0

Since all comparison sort algorithms take at least n lg n time, why would we ever need to use something like quicksort when we can express the items in the quicksort list as bits and using something like radix sort which is linear?

Alkorizm
  • 23
  • 3
  • 1
    Because not everything can be properly compared by just comparing its bits. For example, my logic for `foo1 < foo2` does some complicated logic. – AndyG Oct 01 '14 at 15:00
  • But a floating point is simply 32 bits, so are you saying for lower numbers quicksort is better even though of course asymptotically it isn't? – Alkorizm Oct 01 '14 at 15:01
  • I see, but you couldn't make some kind of integer key for your logic? Wouldn't that work? – Alkorizm Oct 01 '14 at 15:02
  • It would be redundant if you had to recompute the key given the context of the situation, which very well may happen. The point is that bitwise sorting cannot be applied to every situation. – AndyG Oct 01 '14 at 15:04
  • duplicate of a duplicate of a duplicate of a duplicate of a.... – Karoly Horvath Oct 01 '14 at 15:16
  • Your question indicates a fundamental lack of understanding of how radix sort works, and how it differs from comparison sorting. You should read the relevant Wikipedia articles, and follow up on the references. Start here: http://en.wikipedia.org/wiki/Radix_sort – Jim Mischel Oct 01 '14 at 15:21
  • I should note that "linear" is correct but misleading. Radix sort could use an incredible amount of memory if you treated every object by just its bits; another oft-cited reason to use comparison sorts even when elements could be sorted with a non-comparison sort. – AndyG Oct 01 '14 at 15:22

2 Answers2

2

Radix sort tends to exhibit poor cache locality, see for example this paper for an analysis of different sorting algorithms under the influence of cache (skip to the conclusion for a discussion of radix sort's poor cache locality compared to quicksort and mergesort). Quicksort and mergesort partition the data such that after a few iterations a partition will fit on a few cache lines, whereas radix sort keeps shuffling the data. In addition, radix sort either needs to use linked data structures for its buckets (which exhibit poor cache performance), or else it needs to use over-large arrays (which waste memory).

Also, depending on radix sort's radix size, its constant factor may be larger than quicksort's / mergesort's log factor. In an extreme case, using a radix of 2 on 64-bit integers, radix sort has a constant factor of 64 (one pass per bit), whereas it's highly unlikely that quicksort's / mergesort's log factor is that large (as this would imply that you're sorting 2^64 elements)

Zim-Zam O'Pootertoot
  • 17,888
  • 4
  • 41
  • 69
  • Your second point is especially clear when the items aren't scalar values. Imagine trying to use radix sort on an array of 100-character strings. – Jim Mischel Oct 01 '14 at 15:22
  • You're only discussing crappy implementations of LSD radix sort here. A good implementation of MSD radix sort has none of the issues you suggest on uniformly-distributed inputs. – tmyklebu Oct 01 '14 at 15:49
  • @JimMischel: As it happens, radix sort is what people use to sort large arrays of 100-character strings. (Or at least to break it down into a bunch of arrays short enough that in-cache sorting is appropriate.) – tmyklebu Oct 01 '14 at 16:05
1

Modern implementations of mergesort using a SIMD kernel to sort short arrays can be very, very fast. This paper by some folks at Intel describes one such implementation. The chief advantage here is that the SIMD kernel can do several comparisons and swaps per clock cycle, gaining and taking advantage of several bits of information about the array to be sorted per clock cycle.

Quicksort requires a test, a store, and an increment of one of two pointers at each iteration, which forms a single huge dependency chain. This isn't great, since it means you're gaining one bit of information about the array every few clock cycles.

Radix sorts have the same problem as Quicksort (each pass is a single huge dependency chain with an access and increment of one pointer from a largish, uniformly-distributed set). However, on uniformly-distributed inputs, a properly implemented MSD radix sort using five- or six-bit keys can do in one pass over the input what Quicksort will take five or six passes to do. I haven't timed this stuff recently, but a good MSD radix sort might still be the best way to sort large arrays of ints or long longs.

None of this stuff about radix sort will keep you warm at night if your input is badly distributed and the universe of possible keys is large when compared to the number of keys in your input.

tmyklebu
  • 13,915
  • 3
  • 28
  • 57