Algorithms: Efficient Sorting

1. When You need the k-th smallest item or the median, not the whole order

   , choose

   Quickselect

2. When Integer keys span a range not much larger than the number of items, with room for a count per value

   , choose

   Counting Sort

3. When Keys have a fixed number of digits, with room for a second array

   , choose

   Radix Sort

4. When Keys are numbers spread evenly over a known range

   , choose

   Bucket Sort

5. When Equal keys must keep their input order, and there is room for n more items

   , choose

   Merge Sort

6. When There is room for only a few variables, and every input must finish in O(n log n)

   , choose

   Heapsort

7. When Average speed matters most, and a rare O(n²) input is acceptable

   , choose

   Quicksort

8. When Nothing above constrains the program

   , choose

   Built-In Sorts

Each decides the order by comparing two keys at a time, so none can beat O(n log n) in the worst case.

• Merge Sort

  Split in half, sort each half, then merge the two sorted halves into one.

  Use when

  Equal keys must keep their input order, there is room for n more items, or the items are in a linked list.

  Facts

  Time

  O(n log n)

  every case, log n levels of linear merging

  Extra space

  O(n)

  worst case, the merge buffer

  Stable

  yes

  when ties are taken from the left half

• Quicksort

  Partition around a pivot so smaller keys go left and larger go right, then sort each side.

  Use when

  Average speed matters most, and a rare O(n²) input is acceptable.

  Facts

  Time

  O(n log n)

  best and average case, partitions near the middle

  Time

  O(n²)

  worst case, each pivot the smallest or largest key

  Stack

  O(log n)

  worst case, recursing into the smaller side first

• Heapsort

  Build a max-heap in the array, then move its largest item to the end, one at a time.

  Use when

  Memory is fixed at a few variables, and every input must finish in O(n log n).

  Facts

  Time

  O(n log n)

  every case, n sifts of O(log n) each

  Extra space

  O(1)

  every case, the heap lives in the array

  Stable

  no

  in general, the swap to the end reorders equal keys

• Built-In Sorts

  Each language's own sort: stable in Python and TypeScript, and in Java for objects.

  Use when

  Nothing about the keys, the memory or the worst case rules a sort out.

  Facts

  Python sorted, list.sort

  stable

  for every input, an adaptive merge sort

  Java Arrays.sort on objects, List.sort

  stable

  for every input

  TypeScript Array.prototype.sort

  stable

  since ES2019, strings unless given a comparator

Each reads the keys' values or digits instead of comparing them, which is how they pass the n log n bound.

• Counting Sort

  Count how many keys take each value, then place each item at its counted position.

  Use when

  Integer keys in a range not much larger than the number of items.

  Facts

  Time

  O(n + k)

  every case, k possible key values

  Extra space

  O(n + k)

  every case, the counts and the output

  Stable

  yes

  when items are placed from the last one back

• Radix Sort

  Sort by one digit at a time, least significant first, with a stable pass for each.

  Use when

  Keys with a fixed number of digits or characters, such as dates, codes or 32-bit integers.

  Facts

  Time

  O(d · (n + b))

  every case, d digits in base b

  Extra space

  O(n + b)

  every case, one counting pass's buffers

  Stable

  yes

  in every case, each pass is a stable counting sort

• Bucket Sort

  Spread the keys over buckets by value, sort each bucket, then read the buckets in order.

  Use when

  Numbers spread evenly over a known range.

  Facts

  Time

  O(n + b)

  best and average case, keys spread evenly over b buckets

  Time

  O(n²)

  worst case, every key in one bucket

  Extra space

  O(n + b)

  every case, the buckets

Two tools from the same topics that answer something other than the full order: one rank, or a recursion's cost.

• Quickselect

  Partition as quicksort does, then continue only on the side that holds the k-th position.

  Use when

  You need the k-th smallest item or the median, not the whole order.

  Facts

  Time

  O(n)

  expected, with a random pivot

  Time

  O(n²)

  worst case, each pivot the smallest or largest key

• Master Theorem

  T(n) = a·T(n/b) + f(n) solves by comparing f(n) with the leaves' work, n^(log_b a).

  Use when

  A recursion makes a calls on parts of size n/b, and you need its cost without summing a tree.

  Facts

  Binary search, T(n/2) + O(1)

  O(log n)

  worst case

  Largest by halves, 2T(n/2) + O(1)

  O(n)

  every case

  Merge sort, 2T(n/2) + O(n)

  O(n log n)

  every case

1. 01

   Assuming every recursion that halves its input costs O(n log n), when four half-size calls make it O(n²).

   Assuming Every Halving Recurrence Is O(n log n)

2. 02

   Taking from the right half on a tie, which reorders equal keys and breaks stability.

   Taking From the Right Half on a Tie

3. 03

   Taking the last element as the pivot, which makes sorted, reversed and all-equal input cost O(n²).

   Taking the Last Element as Pivot on Sorted Input

4. 04

   Sifting down past the end of the heap, into the sorted part already placed.

   Sifting Down Past the End of the Heap

5. 05

   Placing items front to back with end positions in a radix sort's counting pass, which reverses equal digits.

   Placing Items Front to Back in a Radix Sort's Counting Pass

6. 06

   Sorting numbers in TypeScript without a comparator, which compares them as strings so 100 comes before 9.

   Sorting Numbers in TypeScript Without a Comparator

• Divide and Conquer4 questions

  Practise

• Merge Sort4 questions

  Practise

• Quicksort4 questions

  Practise

• Heapsort3 questions

  Practise

• Linear-Time Sorting5 questions

  Practise

• Choosing a Sorting Algorithm4 questions

  Practise