Computer Science · Lesson 13

Sorting Algorithms

Algorithms Big-O Bubble Sort Merge Sort Quicksort

From shuffled decks to billions of database records, computers sort data constantly. Bubble sort, merge sort, and quicksort tackle the same problem — "put these in order" — in radically different ways, with enormous consequences for speed.

Who Was Donald Knuth?

Donald Knuth (1938–present) is an American computer scientist and mathematician at Stanford University, often called the "father of algorithm analysis." His multi-volume masterwork The Art of Computer Programming — begun in 1962 and still being written — is the most comprehensive treatment of algorithms ever compiled. Knuth formalized Big-O notation as a rigorous language for describing how algorithms scale, and his painstaking analysis of sorting algorithms established the mathematical foundations that every computer scientist still uses today. He also created the TeX typesetting system and famously offers a $2.56 reward for any error found in his books.

Big-O Complexity — How Fast Is "Fast"?

Big-O notation describes how an algorithm's time (or space) grows as input size n increases. It captures the worst-case growth rate, ignoring constants.

O(n²) vs O(n log n) vs O(n)

For n = 1,000: O(n²) ≈ 1,000,000 operations · O(n log n) ≈ 10,000 operations · O(n) ≈ 1,000 operations

The difference between O(n²) and O(n log n) sounds abstract — until n = one billion database records, and the difference is hours vs. seconds.

Algorithm	Best Case	Average	Worst Case	Notes
Bubble Sort	O(n)	O(n²)	O(n²)	Simple but slow; only good for nearly-sorted data
Merge Sort	O(n log n)	O(n log n)	O(n log n)	Always fast; divide and conquer; stable
Quicksort	O(n log n)	O(n log n)	O(n²)	Very fast in practice; worst case rare with good pivot

Sorting Visualiser

Select an algorithm and click Start. Bars being compared are shown in orange; sorted bars turn green. Use the panel controls to change algorithm, speed, and array size.

AlgorithmBubble

Steps0

Comparisons0

Real-World Applications

🔍

Database Indexing Search engines sort billions of results by relevance score in milliseconds. Google's infrastructure runs highly optimised merge-sort variants over enormous datasets.

📁

File Systems Every time you view a folder sorted by name, date, or size, the OS runs a sorting algorithm. Modern file systems use Timsort — a hybrid of merge sort and insertion sort.

🧬

Genomics DNA sequence alignment requires sorting enormous strings of base pairs. Merge-sort variants are used to align genome reads efficiently in bioinformatics pipelines.

🎨

Graphics Rendering The painter's algorithm sorts 3D objects by depth before drawing them back-to-front. Sorting is critical for correct transparency and shadow rendering in real-time graphics.

Practice Problems

Easy1. Bubble sort works by comparing and possibly swapping adjacent elements. True or False?

Hint: Bubble sort repeatedly steps through the list and swaps adjacent elements that are in the wrong order — that is its defining operation.

Easy2. How many comparisons does bubble sort need in the worst case for n = 4? (Worst case = n × (n−1) / 2)

Hint: n×(n−1)/2 = 4×3/2 = 6 comparisons.

Medium3. Merge sort splits an array in half repeatedly. For an array of 8 elements, how many levels of splitting occur before you reach single-element subarrays? (log₂ 8 = ?)

Hint: log₂(8) = 3. At each level the subarrays halve: 8 → 4 → 2 → 1.

Medium4. Quicksort's worst case happens when the chosen pivot is always the smallest or largest element. What is that time complexity?

Hint: A bad pivot always creates one subarray of size n−1 and one of size 0. This gives O(1) + O(2) + … + O(n) = O(n²).

Challenge5. An array of 1,024 items is sorted with merge sort. Merge sort needs approximately n · log₂(n) comparisons. How many comparisons is that? (log₂ 1024 = 10)

Hint: 1,024 × log₂(1,024) = 1,024 × 10 = 10,240 comparisons.