Difficulty: Beginner to Intermediate | Prerequisites: Arrays, loops, searching algorithms basics
Sorting is the process of arranging elements in a specific order (usually ascending). It underpins almost everything else in computer science: searching is faster on sorted data, databases rely on sorted indices, and many real-world problems reduce to "put things in order, then act on them." This material covers four sorting approaches: bubble sort, selection sort, merge sort, and quick sort. The first two are simpler but slower; the last two use a technique called divide and conquer to sort more efficiently. Understanding the mechanics of each, and when to choose one over another, is a core APCS skill.
Bubble sort repeatedly swaps adjacent out-of-order elements. Selection sort finds the minimum and places it in position. Both are O(n²). Merge sort and quick sort split the problem in half, sort the halves, and recombine, achieving O(n log n) on average. Know the swap counts, the step-by-step traces, and which algorithms use divide and conquer.
Bubble sort
A sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. Each pass "bubbles" the largest unsorted element to its correct position. Think of it as the heaviest ball sinking to the bottom of a tube on each shake.
Selection sort
A sorting algorithm that divides the list into a sorted portion and an unsorted portion. On each pass, it finds the minimum element in the unsorted portion and swaps it into position at the end of the sorted portion. Think of it as picking the smallest card from a hand and placing it on the table, one at a time.
Merge sort
A divide-and-conquer sorting algorithm that splits the list in half, recursively sorts each half, and then merges the two sorted halves back together. Think of it as splitting a deck of cards into smaller and smaller piles, sorting each tiny pile, then merging them back in order.
Quick sort
A divide-and-conquer sorting algorithm that selects a "pivot" element, partitions the remaining elements into those less than and greater than the pivot, and recursively sorts each partition. Think of it as choosing a middle-ground card and tossing everything smaller to the left and everything bigger to the right.
Divide and conquer
An algorithm design strategy that breaks a problem into smaller sub-problems of the same type, solves each one, and combines the results. In simple terms, split the big job into small jobs, handle each small job, then piece the answers together.
Pass (in sorting)
One complete traversal through the unsorted portion of the data. Each pass brings at least one element closer to its final position.
Swap / exchange
The operation of switching two elements' positions in the array.
Compare adjacent pairs from left to right.
If the left element is larger than the right, swap them.
After one full pass, the largest element has moved to the end.
Repeat for the remaining unsorted portion.
Continue until a full pass produces no swaps (the array is sorted).
Worked example: Sort {2, 5, 1, 3, 4} using bubble sort.
Pass 1:
2 and 5: no swap → {2, 5, 1, 3, 4}
5 and 1: swap → {2, 1, 5, 3, 4}
5 and 3: swap → {2, 1, 3, 5, 4}
5 and 4: swap → {2, 1, 3, 4, 5} (3 swaps this pass)
Pass 2:
2 and 1: swap → {1, 2, 3, 4, 5} (1 swap this pass)
Remaining comparisons produce no swaps.
Total swaps: 4.
Find the minimum element in the entire unsorted array.
Swap it with the element at the first unsorted position.
Move the boundary of the sorted portion one position to the right.
Repeat until the entire array is sorted.
Key fact: selection sort makes at most one swap per pass. This is a commonly tested point.
Worked example: Sort {5, 3, 8, 1} using selection sort.
Pass 1 (i = 0): Minimum is 1 at index 3. Swap with index 0 → {1, 3, 8, 5}. Pass 2 (i = 1): Minimum of remaining {3, 8, 5} is 3, already at index 1. No swap → {1, 3, 8, 5}. Pass 3 (i = 2): Minimum of remaining {8, 5} is 5 at index 3. Swap with index 2 → {1, 3, 5, 8}.
Array is sorted in 3 passes.
The standard selection sort implementation:
for (i = 0; i < n - 1; i++) {
minIndex = i;
for (j = i + 1; j < n; j++)
if (list[j] < list[minIndex])
minIndex = j;
if (minIndex != i) {
tmp = list[i];
list[i] = list[minIndex];
list[minIndex] = tmp;
}
}
The inner loop finds the index of the smallest element in the unsorted portion. The outer loop places that element. Tracing the array state after each outer-loop iteration is a standard exam task.
Both merge sort and quick sort use the divide-and-conquer strategy. This is frequently tested as a direct question.
Merge sort:
Split the array in half.
Recursively sort each half.
Merge the two sorted halves by comparing elements from each and placing them in order.
Average and worst case: O(n log n). Requires additional memory for the merge step.
Quick sort:
Choose a pivot element.
Partition: move elements smaller than the pivot to its left, larger to its right.
Recursively sort the left and right partitions.
Average case: O(n log n). Worst case (poor pivot choice): O(n²). Sorts in place, so less extra memory than merge sort.
Bubble sort maximum swaps: For an array of n elements, worst case is n(n − 1) / 2 swaps (when the array is in reverse order).
Selection sort swaps per pass: Exactly 0 or 1. At most 1 swap per pass, at most n − 1 swaps total.
Time complexity summary:
Algorithm | Best Case | Average Case | Worst Case |
|---|---|---|---|
Bubble sort | O(n) | O(n²) | O(n²) |
Selection sort | O(n²) | O(n²) | O(n²) |
Merge sort | O(n log n) | O(n log n) | O(n log n) |
Quick sort | O(n log n) | O(n log n) | O(n²) |
Selection sort is used in embedded systems where memory is extremely limited and the dataset is small. Merge sort is the basis of the external sort used when data is too large to fit in memory (sorting files on disk). Quick sort, or a hybrid variant of it, is the default sorting algorithm in most standard libraries (Java's Arrays.sort() for primitives uses a dual-pivot quicksort).
"Selection sort makes many swaps." It makes at most one swap per pass. It does many comparisons, but the swap count is low.
"Bubble sort is always the worst sorting algorithm." For nearly sorted data, bubble sort with an early-exit optimisation can finish in O(n), which is better than selection sort's O(n²) in all cases.
"Merge sort and quick sort are the same thing because they both divide and conquer." Merge sort splits first and does the work during the merge step; quick sort does the work during the partition step and splits are a by-product.
"Quick sort is always O(n log n)." Its worst case is O(n²), which occurs when the pivot is consistently the smallest or largest element.
⚠️ "Which sorting methods use divide and conquer?" is a direct exam question. Answer: merge sort and quick sort.
⚠️ You will be asked to count the exact number of swaps for bubble sort on a given array. Trace carefully, pass by pass.
⚠️ Selection sort's "one swap per pass" fact is frequently tested.
⚠️ Code-trace questions will give you a selection sort implementation and ask you to draw the array after each iteration. Practise this on paper.
True or false: Selection sort performs at most one swap per pass through the list. Answer: True.
Fill in the blank: The two sorting algorithms that use divide and conquer are ___ and ___. Answer: Merge sort and quick sort.
True or false: Bubble sort's worst case is O(n log n). Answer: False. It is O(n²).
Q: How many swaps are needed to sort {2, 5, 1, 3, 4} using bubble sort? Show your working.
A: Pass 1 swaps 5&1, 5&3, 5&4 (3 swaps), giving {2, 1, 3, 4, 5}. Pass 2 swaps 2&1 (1 swap), giving {1, 2, 3, 4, 5}. Total: 4 swaps.
Q: Trace selection sort on {5, 3, 8, 1}. Show the array after each pass.
A: After pass 1: {1, 3, 8, 5}. After pass 2: {1, 3, 8, 5} (no swap needed). After pass 3: {1, 3, 5, 8}.
Q: How many exchanges does selection sort make, at most, at the end of every pass?
A: One. It finds the minimum in the unsorted portion and performs a single swap to place it.
Q: Which divide-and-conquer sort requires extra memory for merging?
A: Merge sort.
Sorting connects directly to searching: binary search requires sorted data, so the choice of sort affects overall performance. Growth-rate functions (covered in the searching notes) are how you compare these algorithms formally. Recursion, which you may study next, is the mechanism that makes merge sort and quick sort work.
sorting algorithms, bubble sort, selection sort, merge sort, quick sort, divide and conquer, swap count, exchange count, pass, O(n²), O(n log n), time complexity, APCS sorting, sort trace, selection sort code, algorithm comparison, in-place sort, stable sort