K-sort: A new sorting algorithm that beats Heap sort for n <= 70 lakhs! by Kiran Kumar Sundararajan, Mita Pal, Soubhik Chakraborty, N.C. Mahanti.
From the description:
Sundararajan and Chakraborty (2007) introduced a new version of Quick sort removing the interchanges. Khreisat (2007) found this algorithm to be competing well with some other versions of Quick sort. However, it uses an auxiliary array thereby increasing the space complexity. Here, we provide a second version of our new sort where we have removed the auxiliary array. This second improved version of the algorithm, which we call K-sort, is found to sort elements faster than Heap sort for an appreciably large array size (n <= 70,00,000) for uniform U[0, 1] inputs.
OK, so some people have small data, < = 70 lakhs to sort at one time. 😉 Also shows that there are still interesting things to say about sorting. An operation that is of interest to topic mappers and others.
This is interesting, but unfortunately an ultimate limit of O(n log n) has been proven for sorting algorithms that rely on swapping data elements. So you can’t take this very far, unfortunately.
Still, better than heapsort is pretty damn good. Of course, Quicksort is better still.
Comment by larsga@garshol.priv.no — July 21, 2011 @ 2:52 am
Thanks!
BTW, there is a very nice visualization of quicksort at Wikipedia:
http://en.wikipedia.org/wiki/Quicksort
Along with comments about parallel implementations.
Comment by Patrick Durusau — July 21, 2011 @ 5:58 am