Sorting

Checkpoints

• Bubble Sort Basis Bubble sort repeatedly walks the array, swapping adjacent out-of-order pairs until no swaps are needed. This checkpoint develops the algorithm, proves it is correct, and explains why its O(n²) worst case makes it a teaching example rather than a practical tool.
• Bucket Sort Basis Bucket sort distributes elements into a fixed number of buckets based on a key function, sorts each bucket, then concatenates the results. This checkpoint develops the algorithm, explains how its expected O(n) running time depends on the input distribution, and contrasts it with counting sort.
• Counting Sort Basis Counting sort sorts integers from a known small range in O(n+k) time by counting occurrences instead of comparing elements. This checkpoint develops the algorithm, contrasts it with comparison-based sorts, and explains why its linear running time depends critically on the size of the key range k.
• Insertion Sort Basis Insertion sort builds a sorted prefix one element at a time by shifting each new element left until it reaches its correct position. This checkpoint develops the algorithm, proves correctness via a loop invariant, and explains its O(n²) worst case alongside its O(n) best case on nearly-sorted input.
• Merge Sort Basis Merge sort divides an array in half, recursively sorts each half, and merges the two sorted halves back together, achieving O(n log n) time in all cases. This checkpoint develops the algorithm in Zig, proves correctness via loop invariants, and explains why the divide-and-conquer structure guarantees a better worst case than quadratic sorts.
• Quick Sort Basis Quick sort picks a pivot element, partitions the array so that everything smaller is to its left and everything larger to its right, then recursively sorts each side, achieving O(n log n) expected time. This checkpoint develops the partition step, analyses average and worst-case complexity, and explains how pivot choice affects performance.
• Radix Sort Basis Radix sort sorts integers digit by digit from least significant to most significant, using a stable subroutine such as counting sort at each pass, achieving O(nk) time where k is the number of digits. This checkpoint develops the algorithm, proves why stability of the inner sort is essential, and analyses when radix sort outperforms comparison-based O(n log n) algorithms.
• Selection Sort Basis Selection sort sorts an array by repeatedly finding the minimum of the unsorted suffix and swapping it into place. This checkpoint develops the algorithm, proves it produces a sorted array, and analyses why it always performs Θ(n²) comparisons regardless of the input.