P-5.3 Sorting

Work through these

• The quadratic sorts, and why they are still worth writing once

  Selection, insertion and bubble sort are slow on large inputs and genuinely competitive on small ones, which is why real libraries fall back to insertion sort below a threshold.

• Merge sort: divide, sort each half, merge

  The recursion splits until sorting is trivial and the work happens on the way back up. Its cost is the same on every input, which is the property quicksort lacks.

  Algorithms, 4th Edition — companion site · Reference

• Quicksort: partition around a pivot, and the worst case

  Choosing a pivot and partitioning around it sorts in place and is very fast in practice. A consistently bad pivot degrades it to quadratic, which is why real implementations randomise or sample.

• Why no comparison sort can beat linear times logarithmic

  There are more possible orderings than a shorter sequence of yes-or-no comparisons can distinguish between. It is a counting argument and it is worth following once, because it is a proof about every algorithm rather than about one.

• Stability, and sorting by one field then another

  A stable sort leaves equal items in their original relative order, which is what lets you sort by name and then by department and keep both. An unstable sort silently discards the first ordering.