Difficulty: Introductory–Intermediate | Prerequisites: Arrays, loops, recursion basics
Sorting is one of the foundational problems in computer science, and most data-processing tasks depend on it in some form. This material covers five classical comparison-based sorting algorithms: selection sort, bubble sort, insertion sort, merge sort, and quick sort. You need a solid grasp of arrays, loops, and basic recursion before diving in. Understanding how these algorithms differ in design and performance is essential for choosing the right tool in practice, and it is heavily tested.
Five sorting algorithms, each with different trade-offs. Bubble, selection, and insertion sort are simple but slow on large inputs (O(n²) worst case). Merge sort and quick sort use divide-and-conquer to achieve much faster average performance (O(n log n)), though quick sort can degrade to O(n²) in the worst case.
Comparison-based sorting
A sorting method that determines order by comparing pairs of elements. All five algorithms covered here are comparison-based. Think of it as: the algorithm can only ask "is A bigger than B?" to make decisions.
In-place sorting
A sort that uses only a constant amount of extra memory beyond the input array. In simple terms, it rearranges the data where it already lives rather than copying everything into a new structure.
Stable sort
A sort that preserves the relative order of elements with equal keys. If two items are "tied," they stay in the same order they started in. Think of it as: a polite sort that does not shuffle things it does not need to.
Divide and conquer
An algorithm design strategy that breaks a problem into smaller sub-problems, solves each recursively, and combines the results. Merge sort and quick sort both follow this pattern.
Time complexity
A measure of how the number of operations an algorithm performs grows as the input size grows. Expressed in Big-O notation (e.g., O(n²), O(n log n)).
Pivot (quick sort)
The element chosen to partition the array during quick sort. Everything smaller goes to one side, everything larger to the other. The choice of pivot heavily influences quick sort's performance.
Scans the unsorted portion of the array, finds the minimum element, and swaps it into the correct position
Repeats for each position from left to right
Always performs O(n²) comparisons regardless of input order
In-place, not stable
Simple to implement but offers no advantage on nearly sorted data
Repeatedly walks through the array, swapping adjacent elements that are out of order
After each full pass, the largest unsorted element "bubbles" to its correct position at the end
Worst and average case: O(n²). Best case (already sorted, with an early-exit flag): O(n)
In-place and stable
Rarely used in practice because it is consistently slower than insertion sort on the same inputs
Builds the sorted portion one element at a time by picking the next unsorted element and inserting it into its correct position among the already-sorted elements
Best case (already sorted): O(n). Worst and average case: O(n²)
In-place and stable
Performs very well on small arrays or nearly sorted data, which is why it is sometimes used as the base case inside more advanced algorithms
Divides the array in half recursively until each sub-array has one element
Merges pairs of sorted sub-arrays back together in order
Always O(n log n) in all cases (best, average, worst)
Stable but not in-place: requires O(n) extra memory for the merge step
Predictable performance makes it a safe default when memory is not a constraint
Picks a pivot element, partitions the array so that elements less than the pivot go left and elements greater go right, then recurses on each partition
Average case: O(n log n). Worst case (poor pivot choice, e.g., already sorted data with first-element pivot): O(n²)
In-place (ignoring recursion stack) but not stable
Typically the fastest in practice due to good cache behaviour and low constant factors, despite the theoretical worst case
Algorithm | Best Case | Average Case | Worst Case | Space | Stable? |
|---|---|---|---|---|---|
Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
The space column refers to auxiliary space beyond the input. Quick sort's O(log n) comes from the recursion call stack.
Merge sort's guaranteed O(n log n) behaviour is why many standard library sort functions (e.g., Python's Timsort, Java's Arrays.sort for objects) are built on merge-sort variants. Quick sort's excellent average-case performance and cache-friendliness make it the default in C's qsort and many systems-level implementations.
Students often assume quick sort is always faster than merge sort. It is not. Quick sort degrades to O(n²) with poor pivot selection, while merge sort stays O(n log n) regardless.
Bubble sort and selection sort are frequently confused. Selection sort finds the minimum and swaps once per pass. Bubble sort swaps adjacent elements repeatedly. They are different algorithms with different swap counts.
"In-place" does not mean "no extra memory at all." It means extra memory usage is constant (O(1)), not proportional to input size. Merge sort's O(n) auxiliary array is why it is not in-place.
Students sometimes think stable vs unstable only matters for numbers. Stability matters whenever records have multiple fields, and you want to preserve a prior ordering on one field while sorting by another.
⚠️ You will almost certainly be asked to compare time complexities across all five algorithms. Memorise the table above.
⚠️ Be prepared to explain why quick sort's worst case is O(n²) and what causes it (sorted input with a bad pivot).
⚠️ Know which algorithms are stable and which are not. This is a common short-answer or true/false question.
⚠️ Understand why merge sort needs extra memory and the others do not.
True or False: Bubble sort is always slower than selection sort.
Fill in the blank: Merge sort's worst-case time complexity is _______.
True or False: Quick sort is a stable sorting algorithm.
Fill in the blank: An in-place algorithm uses at most _______ extra memory.
True or False: Insertion sort performs best when the input is already sorted.
Answers: 1. False (bubble sort can be O(n) on sorted input with early exit). 2. O(n log n). 3. False. 4. O(1) / constant. 5. True.
Q: Why is merge sort preferred over quick sort when worst-case guarantees matter?
A: Merge sort is always O(n log n) regardless of input order, while quick sort can degrade to O(n²) with poor pivot choices. When predictable performance is required, merge sort is the safer choice.
Q: What is the trade-off merge sort makes for its guaranteed O(n log n) performance?
A: It requires O(n) additional memory for the temporary arrays used during merging. The other O(n²) algorithms are all in-place.
Q: If you had a small, nearly sorted array, which algorithm would likely perform best and why?
A: Insertion sort. On nearly sorted data its inner loop does very little work, giving it near-O(n) performance. Its low overhead also makes it faster than merge sort or quick sort on small inputs.
Q: Explain in one sentence why quick sort has O(n²) worst-case complexity.
A: If the pivot is always the smallest or largest element (e.g., first element on sorted data), each partition removes only one element, producing n levels of recursion with O(n) work each.
Q: Name two stable sorting algorithms from this unit.
A: Bubble sort, insertion sort, and merge sort are all stable. (Any two of the three is correct.)
This material connects directly to Big-O notation and algorithm analysis, which you will use throughout the rest of the course. The divide-and-conquer pattern from merge sort and quick sort reappears in binary search, tree operations, and many later algorithms. Understanding these trade-offs also prepares you for data-structures topics where sorted input is a precondition (e.g., binary search trees, priority queues).
sorting algorithms, comparison sort, selection sort, bubble sort, insertion sort, merge sort, quick sort, quicksort, time complexity, Big-O, O(n²), O(n log n), in-place sort, stable sort, divide and conquer, pivot, partition, COP3502C, Computer Science I, UCF, algorithm efficiency, runtime comparison