6 ms·

Despite that no real-world quicksort implementations have that worst case (due to fallbacks to other sorts), it seems like it's useful to see the pathological c

• TheLoneWolfling 12y ago
  At which case: why bother using quicksort?
  • mjcohen 12y ago
    It's simple(relatively) and almost always quite fast. Or would you rather use slowsort?
    • TheLoneWolfling 12y ago
      Quicksort is not simple if you have to build in an entire other sorting algorithm as a failsafe. And merge sort is often faster, especially if the comparison function is relatively expensive.
      • RogerL 12y ago
        Yes, sometimes, but it also uses more memory. In practice, with real problems, quicksort wins with in-memory sorting, and mergesort wins with too big for memory data sets.
  • jemfinch 12y ago
    Because in the real world, where all our code must actually run, quicksort beats practically every other algorithm on the vast majority of inputs. Its cache behavior is better than heap sort, its memory usage is lower than merge sort, and even its O(log n) memory usage is efficiently allocated on the stack as opposed to hitting a slow system allocator. "Engineering a Sort Function"[0] covers this quite well. In some experiments of my own, I've found that even Smoothsort[1] (an algorithm specifically designed to have a smooth transition from linear to linearithmic behavior on nearly-sorted input) can't beat the C++ system's introsort (a quicksort variation with a fallback to heapsort) in already-sorted inputs. [0] http://www.skidmore.edu/~meckmann/2009Spring/cs206/papers/spe862jb.pdf http://www.skidmore.edu/~meckmann/2009Spring/cs206/papers/sp... [1] http://www.keithschwarz.com/smoothsort/ http://www.keithschwarz.com/smoothsort/