I just thought of an interesting way to do a sort. I'm sure someone has thought of it before, but I've never seen it. It goes in two steps:

**1-** Iterate through the input list, pulling out sequences of items that are in order (not necessarily contiguous) into bins. Create one bin for each pass, until the list is empty.

**2-** Merge the sorted bins back together using a standard merge (repeated selection of lowest first element)

Here is a prototype I made in Python. The output below might be more illuminating.

```
items = len(unsorted)
sortedBins = []
# Pull out bins of sorted numbers, until the unsorted list is depleted:
while( len(unsorted) > 0 ):
  print "Unsorted list: " + `unsorted`
  highest = float("-inf")
  newBin = []

  i = 0
  while( i < len(unsorted) ):
    # Find items in unsorted list that are in order, pop them out:
    if( unsorted[i] >= highest ):
      highest = unsorted[i]
      newBin.append( unsorted.pop(i) )
    i=i+1

  sortedBins.append(newBin)
  print "bin[%i]: "%(len(sortedBins)-1) + `newBin`
  print

# Merge all of the sorted bins together:
sorted = []
while( len(sorted) < items ):
  lowBin = 0
  for j in range( 0, len(sortedBins) ):
    if( sortedBins[j][0] < sortedBins[lowBin][0] ):
      lowBin = j
  print "lowBin: %i: %i" % (lowBin, sortedBins[lowBin][0])
  sorted.append( sortedBins[lowBin].pop(0) )
  if( len(sortedBins[lowBin]) == 0 ):
    del sortedBins[lowBin]

print "sorted:" + `sorted`

```

It seems like the worst case (a completely reversed list) would take **n(n+1)** time if I'm not crazy (that is, n(n+1)/2 for each loop). The best case (an already sorted list) would take **2\*n** time.

**EDIT:** It runs now, so stop complaining. Here is the output, which further demonstrates how it works:

```
Unsorted list: [1, 4, 3, 8, 3, 7, 9, 4, 8, 9, 3]
bin[0]: [1, 3, 3, 9, 9]

Unsorted list: [4, 8, 7, 4, 8, 3]
bin[1]: [4, 7, 8]

Unsorted list: [8, 4, 3]
bin[2]: [8]

Unsorted list: [4, 3]
bin[3]: [4]

Unsorted list: [3]
bin[4]: [3]

lowBin: 0: 1
lowBin: 0: 3
lowBin: 0: 3
lowBin: 4: 3
lowBin: 1: 4
lowBin: 3: 4
lowBin: 1: 7
lowBin: 1: 8
lowBin: 1: 8
lowBin: 0: 9
lowBin: 0: 9
sorted:[1, 3, 3, 3, 4, 4, 7, 8, 8, 9, 9]

```