Strand sort
Strand sort je algoritam za sortiranje koji radi tako što konstantno izvlači sortirane podnizove iz niza koji treba sortirati i spaja ih u rezultujući niz. Svaka iteracija kroz nesortirani niz izvlači elemente koji su već sortirani i spaja ih.

Ime algoritma potiče od lanaca sortiranih podataka u nizu koji treba sortirati i koji se izvlače iz niza jedan po jedan. Ovo je algoritam baziran na poređenjima, s obzirom na upotrebu poređenja prilikom izvlačenja lanaca i njihovog spajanja u sortiran niz.

Složenost algoritma je O(n2) u prosečnom slučaju. U najboljem slučaju (kada je niz već sortiran) složenost je linearna tj. O(n). U najgorem slučaju (kada je niz obrnuto sortiran) složenost je O(n2).

Strand sort je najkorisniji kod podataka koji se čuvaju u povezanoj listi, zbog čestih umetanja i izvlačenja podataka. Korišćenje drugačije strukture podataka, kao što je niz, dosta povećava vreme izvršavanja i složenost algoritma zbog dužine niza. Ovaj algoritam je koristan i u situacijama kada imamo veliku količinu već sortiranih podataka jer te podatke možemo da izvučemo u jedan lanac.

Primer 

 Iz nesortiranog niza izdvajamo rastuće brojeve.
 U prvoj iteraciji sortirani podniz smeštamo u prazan sortiran niz.
 Iz nesortiranog niza ponovo izdvajamo relativno sortirane brojeve.
 Pošto je sortiran niz popunjen, spajamo podniz u sortiran niz.
 Ponavljati korake 3-4 dok oba niza nisu prazna.

Algoritam 
Pseudokod:
 procedure strandSort(A : niz ) defined as:
   while length(A ) > 0
     clear podniz
     podniz[ 0 ] := A[ 0 ]
     remove A[ 0 ]
     for each i in 0 to length(A ) - 1 do:
       if A[ i ] > podniz[ last ] then
         append A[ i ] to podniz
         remove A[ i ]
       end if
     end for
     merge podniz into rezultat
   end while
   return rezultat
 end procedure

Haskell implementacija 
merge [] l = l
merge l [] = l
merge l1@(x1:r1) l2@(x2:r2) =
    if x1 < x2 then x1:(merge r1 l2) else x2:(merge l1 r2)

ssort [] = []
ssort l = merge strand (ssort rest)
    where (strand, rest) = foldr extend ([],[]) l
          extend x ([],r) = ([x],r)
          extend x (s:ss,r) = if x <= s then (x:s:ss,r) else (s:ss,x:r)

PHP implementacija 
function strandsort(array $arr) {
  $result = array();
  while (count($arr)) {
    $sublist = array();
    $sublist[] = array_shift($arr);
    $last = count($sublist)-1;
    foreach ($arr as $i => $val) {
      if ($val > $sublist[$last]) {
        $sublist[] = $val;
        unset($arr[$i]);
        $last++;
      }
    }

    if (!empty($result)) {
      foreach ($sublist as $val) {
        $spliced = false;
        foreach ($result as $i => $rval) {
          if ($val < $rval) {
            array_splice($result, $i, 0, $val);
            $spliced = true;
            break;
          }
        }

        if (!$spliced) {
          $result[] = $val;
        }
      }
    }
    else {
      $result = $sublist;
    }
  }

  return $result;
}

Python implementacija 
items = len(unsorted)
sortedBins = []
while(len(unsorted) > 0 ):
    highest = float("-inf")
    newBin = []
    i = 0
    while(i < len(unsorted) ):
        if(unsorted[i] >= highest ):
            highest = unsorted.pop(i)
            newBin.append(highest )
        else:
            i=i+1
    sortedBins.append(newBin)

sorted = []
while(len(sorted) < items ):
    lowBin = 0
    for j in range(0, len(sortedBins) ):
        if(sortedBins[j][0] < sortedBins[lowBin][0] ):
            lowBin = j
    sorted.append(sortedBins[lowBin].pop(0) )
    if(len(sortedBins[lowBin]) == 0 ):
        del sortedBins[lowBin]

Reference 
 Paul E. Black "Strand Sort" from Dictionary of Algorithms and Data Structures at NIST.

Референце 

Алгоритми сортирања
Strand sort je algoritam za sortiranje koji radi tako što konstantno izvlači sortirane podnizove iz niza koji treba sortirati i spaja ih u rezultujući niz . Svaka iteracija kroz nesortirani niz izvlači elemente koji su već sortirani i spaja ih . Ime algoritma potiče od lanaca sortiranih podataka u nizu koji treba sortirati i koji se izvlače iz niza jedan po jedan . Ovo je algoritam baziran na poređenjima , s obzirom na upotrebu poređenja prilikom izvlačenja lanaca i njihovog spajanja u sortiran niz . Složenost algoritma je O( n2 ) u prosečnom slučaju . U najboljem slučaju ( kada je niz već sortiran ) složenost je linearna tj . O( n ) . U najgorem slučaju ( kada je niz obrnuto sortiran ) složenost je O( n2 ) . Strand sort je najkorisniji kod podataka koji se čuvaju u povezanoj listi , zbog čestih umetanja i izvlačenja podataka . Korišćenje drugačije strukture podataka , kao što je niz , dosta povećava vreme izvršavanja i složenost algoritma zbog dužine niza . Ovaj algoritam je koristan i u situacijama kada imamo veliku količinu već sortiranih podataka jer te podatke možemo da izvučemo u jedan lanac . Primer Iz nesortiranog niza izdvajamo rastuće brojeve . U prvoj iteraciji sortirani podniz smeštamo u prazan sortiran niz . Iz nesortiranog niza ponovo izdvajamo relativno sortirane brojeve . Pošto je sortiran niz popunjen , spajamo podniz u sortiran niz . Ponavljati korakedok oba niza nisu prazna . Algoritam Pseudokod : procedure strandSort( A \ : niz ) defined as : while length ( A ) > 0 clear podniz podniz [ ] \ := A [ ] remove A [ ] for each i into length ( A ) -do : if A [ i ] > podniz [ last ] then append A [ i ] to podniz remove A [ i ] end if end for merge podniz into rezultat end while return rezultat end procedure Haskell implementacija merge [ ] l = l merge l [ ] = l merge l1@( x1:r1 ) l2@( x2:r2 ) = if x1 < x2 then x1:( merge r1 l2 ) else x2:( merge l1 r2 ) ssort [ ] = [ ] ssort l = merge strand ( ssort rest ) where ( strand , rest ) = foldr extend ( [ ] , [ ] ) l extend x ( [ ] ,r ) = ( [ x ] ,r ) extend x ( s:ss ,r ) = if x <= s then ( x:s:ss ,r ) else ( s:ss, x:r ) PHP implementacija function strandsort( array $arr ) { $result = array ( ) ; while ( count( $arr ) ) { $sublist = array ( ) ; $sublist [ ] = array_shift( $arr ) ; $last = count( $sublist ) -1 ; foreach ( $arr as $i => $val ) { if ( $val > $sublist[ $last ] ) { $sublist [ ] = $val ; unset( $arr[ $i ] ) ; $last++ ; } } if ( !empty( $result ) ) { foreach ( $sublist as $val ) { $spliced = false ; foreach ( $result as $i => $rval ) { if ( $val < $rval ) { array_splice( $result , $i , $val ) ; $spliced = true ; break ; } } if ( !$spliced ) { $result [ ] = $val ; } } } else { $result = $sublist ; } } return $result ; } Python implementacija items = len( unsorted ) sortedBins = [ ] while( len( unsorted ) > ) : highest = float( " -inf " ) newBin = [ ] i = 0 while( i < len( unsorted ) ) : if( unsorted[ i ] >= highest ) : highest = unsorted.pop ( i ) newBin.append ( highest ) else : i=i+1 sortedBins.append ( newBin ) sorted = [ ] while( len( sorted ) < items ) : lowBin = 0 for j in range( 0 , len( sortedBins ) ) : if( sortedBins[ j][ 0 ] < sortedBins[ lowBin ][ 0 ] ) : lowBin = j sorted.append ( sortedBins[ lowBin] .pop( 0 ) ) if( len( sortedBins[ lowBin ] ) == ) : del sortedBins[ lowBin ] Reference Paul E . Black " Strand Sort " from Dictionary of Algorithms and Data Structures at NIST . Референце Алгоритми сортирања