Does this sorting algorithm have a name? (Cross between select and merge) [closed]

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. Closed 11 years ago.

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]

---

I believe that you're looking at strand sort, a modified merge sort that works by locating and removing "strands" of increasing values out of the original array, then merging all the strands back together. It has best-case runtime O(n) if the input sequence is already sorted, and both average- and worst-case runtimes of O(n²), since the algorithm may have to make n passes over the array, each time pulling out just a single element.

So yes, this sorting algorithm has been discovered before, but you're better off just using a standard merge sort because the performance is much better.

Hope this helps!

---

Looks like a selection sort with an optimizing heuristic of starting at the last selected index instead of starting at the beginning, then making up the cost of that in your "merge" sequence. You're right in that it's an O(n^2) algorithm. It would do best with mostly-sorted (in descending order) lists, but I can't really imagine a situation where it would perform better on average than just a selection sort, so I doubt anyone's made/named exactly this algorithm before.

---

Maybe there are some small bugs as others suggested, I am able to follow your logic. I would still call it merge sort, with a modified partitioning strategy.

---

Looks like a bucket sort done backwards. Instead of placing buckets in order and then putting elements in them then sorting them, you are looking to find 'free' sorted buckets (except doing the comparison to determine if they are sorted costs the same as actually sorting a value so it isn't actually 'free' by any means on random data) then placing the sorted buckets in order.

On random data this algorithm will usually yield very few buckets of more than one item, in which case it denigrates to having a useless and expensive loop at the beginning followed by a standard sort in your second loop.