5 ms·
No, the O(n) for median selection is the same O(n) for set partition.
by yters 18y ago
No, 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 agoDoh, right, k select is the same problem. Median of medians is a good linear time technique, though.