Advanced/Non common Efficient Sorting Algorithms

Question

I know there are some like:

• Bubble sort
• Insertion sort
• Shell sort
• Merge sort
• Heapsort
• Quicksort
• Bucket sort
• Radix sort
• Distribution sort
• Shuffle sort

And there are some impractical ones like:

• Bogosort
• RandomSort

Some of the above use comparisons and others do not.

Do you know which other Efficient Algorithms or Techniques for sorting numbers exist? You can suggest me one even if it is not applicable in real life or it is impractical but it must be efficient, but it would be better if it is a computational solution.

Answer 1

Python uses an algorithm called timsort.

Answer 2

Spaghetti sort: You cut lengths of spaghetti to lengths corresponding to numbers you want to sort. Then you tap the bundle of spaghetti down on the table so that all their ends align. Then you pick out the longest ones in order. The setup time is long, but the actual sorting time is constant.

Wikipedia has a whole category of sorting algorithms.

Answer 3

There are sorting networks, which can be an efficient way of sorting if you know in advance how many items you have to sort.

Answer 4

natural mergesort is different enough from "plain mergesort" to be worth mentioning separately (just like quickersort is enough of a variation on quicksort to be worth mentioning, but even more so). Python's timsort, which Ned's answer mentions, is based on natural mergesort, btw.

Oh, and, there's Dobosiewicz sort AKA "comb sort", which "stands to bubblesort as shellsort stands to insertion sort" (nothing especially efficient, but still worth mentioning).

Answer 5

A nice variation of Heapsort is Smoothsort. It performs better than Heapsort if the data is already almost sorted (O(n) instead of O(n log n)).