Strand sort

From Wikipedia, the free encyclopedia

Strand sort is a sorting algorithm. It works by repeatedly pulling sorted sublists out of the list to be sorted and merging them with a result array. Each iteration through the unsorted list pulls out a series of elements which were already sorted, and merges those series together.

The name of the algorithm comes from the "strands" of sorted data within the unsorted list which are removed one at a time. It is a comparison sort due to its use of comparisons when removing strands and when merging them into the sorted array.

The strand sort algorithm is O(n log n) in the average case. In the best case (a list which is already sorted) the algorithm is linear, or O(n). In the worst case (a list which is sorted in reverse order) the algorithm is O(n²).

Strand sort is most useful for data which is stored in a linked list, due to the frequent insertions and removals of data. Using another data structure, such as an array, would greatly increase the running time and complexity of the algorithm due to lengthy insertions and deletions. Strand sort is also useful for data which already has large amounts of sorted data, because such data can be removed in a single strand.

[edit] Example

1. Parse the Unsorted List once, taking out any ascending (sorted) numbers.
2. The (sorted) Sublist is, for the first iteration, pushed onto the empty sorted list.
3. Parse the Unsorted List again, again taking out relatively sorted numbers.
4. Since the Sorted List is now populated, merge the Sublist into the Sorted List.
5. Repeat steps 3-4 until both the Unsorted List and Sublist are empty.

[edit] Algorithm

A simple way to express strand sort in pseudocode is as follows:

procedure strandSort( A : list of sortable items ) defined as:
  while length( A ) > 0
    clear sublist
    sublist[ 0 ] := A[ 0 ]
    remove A[ 0 ]
    for each i in 0 to length( A ) do:
      if A[ i ] > sublist[ last ] then
        append A[ i ] to sublist
        remove A[ i ]
      end if
    end for
    merge sublist into results
  end while
  return results
end procedure

Here is an example of this sort in Java 1.5:

public static <E extends Comparable<? super E>> List<E> sort(Collection<E> coll) 
        {  
                List<E> results = new ArrayList<E>();
                while (!coll.isEmpty())
                {
                        ArrayList<E> sublist = new ArrayList<E>();
                        Iterator<E> i = coll.iterator();
                        sublist.add(i.next());
                        i.remove();
                        while (i.hasNext())
                        {
                                E val = i.next();
                                if (val.compareTo(sublist.get(sublist.size()-1)) >= 0)
                                {
                                        sublist.add(val);
                                        i.remove();
                                }
                        }
                        if (!results.isEmpty())
                        {
                                ListIterator<E> li = results.listIterator();
                                E current = li.next();
                                while (!sublist.isEmpty())
                                {
                                        if (sublist.get(0).compareTo(current) < 0)
                                        {
                                                li.previous();
                                                li.add(sublist.remove(0));
                                        }
                                        else if (li.hasNext())
                                        {
                                                current = li.next();
                                        }
                                        else
                                                break;
                                }
                        }
                        else results.addAll(sublist);
                        sublist.clear();
                }
                return results;
        }

[edit] References

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

v • d • e Sorting algorithms Theory Computational complexity theory | Big O notation | Total order | Lists | Stability | Comparison sort Exchange sorts Bubble sort | Cocktail sort | Odd-even sort | Comb sort | Gnome sort | Quicksort Selection sorts Selection sort | Heapsort | Smoothsort | Strand sort Insertion sorts Insertion sort | Shell sort | Tree sort | Library sort | Patience sorting Merge sorts Merge sort Non-comparison sorts Radix sort | Bucket sort | Counting sort | Pigeonhole sort | Tally sort Others Topological sorting | Sorting network | Bitonic sorter Ineffective/jokeful sorts Bogosort