5 ms·
It also has very consistent asymptotic performance... ie. doesn't degrade as badly as Quicksort when the data is strange in some way. (When a list is already in
by Xichekolas 18y ago
It also has very consistent asymptotic performance... ie. doesn't degrade as badly as Quicksort when the data is strange in some way. (When a list is already in reverse order, naive Quicksort degrades to O(n^2)).
Also oddly interesting, according to some page I was reading on Quicksort before this, there exist adaptive algorithms that generate worst case data sets for Quicksort no matter what the partitioning scheme is.
- eru 18y agoHow general can the partitioning scheme be? Can it generate worst cases for random selection of the pivot? Also one can always select the median in (deterministic) linear time. This way quicksort won't degenerate to O(n^2) ever.
- arebop 18y agoI think Xichekolas had in mind adversarial techniques such as the one described in http://www.cs.dartmouth.edu/~doug/mdmspe.pdf http://www.cs.dartmouth.edu/~doug/mdmspe.pdf. That paper assumes O(1) pivot selection.
- eru 18y agoI read the paper. Seems like they can not beat a median pivot (that takes O(k) to find at each step, but keeps the quicksort runtime of O(n log n).) Still, a cool progam.
- lliiffee 18y agoWith random pivot selection, quicksort is expected O(n log n) time for all inputs. (The expectation is over the set of random numbers used to pick the random pivots, and doesn't involve the input at all). Algorithms like this are called "las-vegas".
- eru 18y agoYes. And if your adversarial algorithm is good enough, it should work even in that case. (Of course any input is the worst case if all inputs have the same expected time.)
- Retric 18y agoWait if finding the median takes n time, and your sort takes n log n time then your best option is ~ n * log n * log n.
- yters 18y agoNo, the O(n) for median selection is the same O(n) for set partition.
- Retric 18y agoAhh, ok, it takes N * log N to do the selection, but it's only O(l) for the length of the set partition each time. I was thinking it's the same n each cycle vs the same n at each depth. Err, nm it's hard to put into words. PS: It still doubles the time but that's not important in O notation.
- eru 18y agoYou can get away with less than the media. For example a pivot guaranteed to lie between the 25th and 75th percentile is good enough and can be found faster.
- Retric 18y agoPersonally, I really like merge sort. It makes few assumptions, it's stable, it works well with sorted inputs, can be split across multiple CPU's, and it works well with sequential input streams. Radix sort tends to be faster especially for strings, but it does not work for many data structures without adapting the algorithm. EX: Radix sorting doubles requires bit manipulation of the data.
- eru 18y agoMerge sort can be thought of as a kind of binary counting.
- yters 18y ago
- dfox 18y agoImportant fact is that burst sort ("string" being the important keyword in title) is not as general as quick sort and thus it can be very fast. With assumptions required by quick sort (having comparison operator) sorting cannot be faster than O(Nlog(N)) (on average). If you are interested in general sorting algorithm with good worst case performance, try merge sort. Merge sort is O(Nlog(N)) independent of input data, but with significantly larger constants than quick sort, also in theory it requires O(N) auxiliary space, but that is only case for arrays, linked-lists can be sorted in place.