Sorting and Complexity Analysis
Lesson 8 of 8
8Sorting and Complexity Analysis (Big O)
The first formal tool for comparing solutions mathematically instead of "I feel like this is faster," and the first real family of sorting algorithms.
What the picture shows: Each step compares two neighbouring bars and swaps them when the bigger one comes first, until the row is sorted.
Map of this part
The concepts in order, click any one to jump to it:
Two ways into the same idea
Sorting a pile of exam papers by name can be done many ways: compare each two neighbours, or split the pile in half, sort each half and merge them. All reach the same result, but some take a minute and some an hour as the pile grows. Complexity analysis measures that difference before you try.
Big-O notation describes how time grows with input size n: bubble and insertion sort are O(n^2), merge and quick sort O(n log n) on average. You count operations in the worst and average cases and watch for stable sorting and extra memory.
Before You Start
🔁Nested loops
Most simple sorting algorithms are built on a loop inside a loop, just like in Part Four.
The Core Idea: What Does Big O Actually Measure?
Big O doesn't measure time in seconds (that depends on the machine's speed), it measures how execution time (or memory usage) grows as input size n grows, usually in the worst case.
Figure 1, every step to the right means much faster time growth as n grows; an O(n²) algorithm on a million elements is roughly a million times slower than an O(n) algorithm on the same count.
11️⃣ O(1), Constant
Same time regardless of input size, like accessing an array element by its direct index. The mechanical reason: any element's address arr[i] is computed directly with one formula (start address + i × element size), with no need to pass through earlier elements at all, whether the array has 10 elements or 10 million, computing that address itself doesn't change.
2O(n), Linear
Time scales directly with input size, like scanning every element of a list once. If checking one element takes one unit of time, checking 10 elements takes 10 units, and 1,000 elements takes 1,000 units, the relationship is a perfectly straight line: double the input and the time doubles by the exact same ratio, no more, no less.
3O(n²), Quadratic
Time scales with the square of input size, common in simple sorting algorithms that compare nearly every pair of elements. The difference matters enormously in practice: doubling the input size in an O(n) algorithm only doubles the time once, but in an O(n²) algorithm it quadruples the time (since (2n)² = 4n²), this is exactly why Bubble Sort is fine on 10 elements but completely impractical on a million, where the comparison count balloons to roughly 500 billion instead of just one million for a linear algorithm.
Comparing Common Sorting Algorithms
| Algorithm | Worst case | Stable? | In-place? | The idea |
|---|---|---|---|---|
| Bubble Sort | O(n²) | Yes | Yes | Swap every unordered adjacent pair, repeat passes until no swap happens |
| Selection Sort | O(n²) | No | Yes | Find the smallest element in the unsorted part and place it correctly, repeat |
| Insertion Sort | O(n²) | Yes | Yes | Build the sorted part element by element, inserting each new element into its correct place within it |
| Merge Sort | O(n log n) | Yes | No | Repeatedly split the list in half down to single elements, then merge them back sorted ascending |
| Quick Sort | O(n²) (rare) | No | Yes | Pick a pivot and partition elements around it, then recursively sort each partition |
Figure 2, Merge Sort splits each level exactly in half, so it only ever needs log n levels; Quick Sort's worst case peels off one element at a time, needing a full n levels, that difference is exactly why one is O(n log n) and the other O(n²).
Worked Example: Tracing Bubble Sort Step by Step
Sorting [5, 2, 4, 1] ascending:
| Pass | Comparisons and swaps | State after the pass |
|---|---|---|
| 1 | 5>2 swap, 5>4 swap, 5>1 swap | [2, 4, 1, 5] |
| 2 | 2<4 no swap, 4>1 swap | [2, 1, 4, 5] |
| 3 | 2>1 swap | [1, 2, 4, 5] ← no swap after this, sorting done |
void bubble_sort(int *array, size_t size)
{
size_t i, j;
int swapped;
for (i = 0; i < size - 1; i++)
{
swapped = 0;
for (j = 0; j < size - i - 1; j++)
{
if (array[j] > array[j + 1])
{
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
swapped = 1;
}
}
if (!swapped) /* no swap = the list is already sorted, stop early */
break;
}
}
Why This Actually Matters
🔎Choosing the right tool
For very small or nearly-sorted input, simple Insertion Sort is actually faster than the more complex Merge Sort; for huge random input, Merge Sort or Quick Sort are far better.
💬A common language in technical interviews
Big O is the standard language for discussing any solution's efficiency, you don't need to actually run code to compare two solutions theoretically.
Deep Dive: Big O, the Algorithms and Stability
Sorting is the ideal example for learning to think in complexity: one problem and dozens of solutions differing by thousands of times in speed. Here we explain each algorithm’s idea away from code, then define the difference between stable and unstable sorting, and how to choose.
1. The language of Big O in numbers
Big O does not measure seconds but how the work grows with the input size n, ignoring constants and small terms. So 3n + 10 is O(n) and n² + n is O(n²). The table below shows why the difference matters, by approximate operation count:
| Class | n = 10 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|
| O(1) | 1 | 1 | 1 |
| O(log n) | ≈ 3 | ≈ 10 | ≈ 20 |
| O(n) | 10 | 1,000 | 1,000,000 |
| O(n log n) | ≈ 33 | ≈ 10,000 | ≈ 20,000,000 |
| O(n²) | 100 | 1,000,000 | 1,000,000,000,000 |
Look at the last row: with a million items a quadratic algorithm needs a trillion operations, hours, while an n log n algorithm needs only twenty million, fractions of a second. That is what makes choosing the algorithm more important than polishing code line by line.
2. The idea behind each algorithm
🫧Bubble
Compares each adjacent pair and swaps them if out of order, so the largest value floats to the end on each pass. It repeats until a pass makes no swap. Simple but O(n²), unless the input is nearly sorted and a swap-free pass is detected.
🃏Insertion
Like arranging playing cards in your hand: take the next item and slot it into its right place among those already sorted. Excellent for small or nearly sorted input (O(n) in its best case).
🎯Selection
Finds the smallest item in the unsorted part and places it at the first unsorted position. It makes few swaps but is always O(n²) in comparisons whatever the input.
⚡Quick
Chooses a pivot and splits the array into what is smaller and what is larger than it, then sorts each part the same way. Average O(n log n) and fast in practice, but consistently poor pivots (for instance the smallest item in a sorted array) bring it to O(n²).
Figure 3, The Quick sort idea: split around the pivot, then handle each part.
3. Stable sorting
Stable sorting preserves the original order of items with equal keys. Example: you have students ordered by name and sort them by grade. In a stable sort students with the same grade stay in name order, while in an unstable sort their order may mix. This matters when sorting by two keys in sequence: a stable sort by the secondary key then by the primary gives the right order. Bubble and Insertion are stable, while Selection and Quick in their simplest forms are not.
| Order | Records (name, grade) |
|---|---|
| Before (ordered by name) | Ali B, Dana A, Omar A, Sara B |
| After a stable sort by grade | Dana A, Omar A, Ali B, Sara B |
| After an unstable sort (one possible result) | Omar A, Dana A, Sara B, Ali B |
Both orders are sorted by grade, but only the stable one keeps Dana before Omar and Ali before Sara as in the original.
4. How do you choose an algorithm?
| Algorithm | Best | Average | Worst | Extra memory | Stable |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
Figure 4, A simplified decision tree for choosing a sort by the input’s properties.
Judging an algorithm by one experiment on a small input. An O(n²) can beat an O(n log n) at small n thanks to its small constants, so do not generalize until you measure on different sizes and varied data (sorted, reversed, random).
Try it yourself
What does Big O measure?
Seconds depend on the machine; Big O describes growth behaviour, usually in the worst case.
If you double the input of an O(n²) algorithm, the time roughly:
Time scales with n squared; doubling gives 2² = 4 times.
Which sorting algorithm is great for small or nearly sorted input (O(n) at best)?
Insertion places each item among the sorted ones, so almost nothing moves on nearly sorted input.
Quick Review Flashcards
Check Your Understanding
Why does the Bubble Sort code above stop early (break) if no swap happened during a full pass?
Because no swap happening means the list is already fully sorted, continuing with additional passes would be wasted work with no benefit.
If you have a very small input (only 5 elements), is it worth using complex Merge Sort instead of simple Bubble Sort?
Usually not, the practical performance difference on such small input is tiny, while the extra code complexity (splitting, merging, extra memory) is only justified at much larger input sizes.
You have a small, nearly sorted array; which algorithm do you pick?
Insertion: it approaches O(n), is stable and simple.
About how many operations does O(n²) need for a million items?
About a trillion.
Resources for this part
Sorted by kind: start with the official docs when you want the precise reference, or with an article or video when you want the explanation first.
Resources for this lesson
Grouped by type. Start with the official docs for precision, or an article or video for the explanation.
Articles1
Tools2
Done with this lesson?
Sign in to save your progress.