4 ms·

Quicksort is actually possible; it's really simple. What really would tick the box is Timsort: https://en.wikipedia.org/wiki/Timsort https://en.wikipedia.org/w

• thaumasiotes 5y ago
  Mergesort and quicksort both work on the principle of sorting both halves of a list separately and then combining them. But mergesort is much simpler than quicksort. Mergesort makes dividing the list in half easy: you just cleave the list at the halfway point. Then it's your job to assemble two small sorted lists into one big sorted list, which is also easy. Quicksort makes assembling the large list easy: everything in the left list is smaller than everything in the right list, so all you need to do is concatenate the two sublists. But we've made something that was already easy even easier at the cost of making dividing the list much more difficult. Now instead of cutting the list in half, we have to rearrange it into a small part on the left and a large part on the right. (Actually, you can just assemble new lists by filtering the input for small numbers (and passing them to the left) and then refiltering for large numbers (and passing them to the right). You're already doing O(n) work on the input, so doing O(n) work two more times won't change the asymptotic complexity. But anyone who's looking for an elegant solution will hate you.)
  • strikelaserclaw 5y ago
    yes, if u don't remember it, it takes a big of thought to how to use two pointers to sort left and right for quicksort