Source: Comprehensive Guide to Sorting Algorithms, Computer Science I (UCF)
Tags: sorting, sorting algorithms, BubbleSort, InsertionSort, SelectionSort, comparison sort, O(n²), quadratic time, in-place sort, adjacent swap, minimum element, sorted sublist, CS 101, computer science fundamentals
Difficulty: Introductory. No prerequisites beyond basic arrays and loops.
Sorting is one of the first algorithmic problems you meet in a CS course, and it keeps showing up everywhere: databases, search engines, operating systems, data analysis pipelines. The reason it gets so much attention is that it is simple enough to state in one sentence ("put these numbers in order") yet rich enough to illustrate most of the big algorithm-design ideas you will encounter later, including divide and conquer, in-place manipulation, and heap structures.
This first set of notes covers the sorting problem itself and three straightforward O(n²) algorithms: BubbleSort, InsertionSort, and SelectionSort. They are slow on large inputs, but understanding them builds the intuition you need before tackling the faster sorts in Part 2.
Sorting means rearranging a sequence so every element is less than or equal to the one after it. BubbleSort, InsertionSort, and SelectionSort all run in O(n²) time in the worst case, but each works differently and has a distinct best-case profile. InsertionSort is the practical pick among the three, especially on small or nearly sorted data.
Sorting problem
Given a sequence of n elements, produce a permutation of those elements in non-decreasing order. In simple terms, this means "rearrange the list so the numbers go from smallest to largest (with ties allowed)."
Non-decreasing order
Each element is less than or equal to the element that follows it (a₁' ≤ a₂' ≤ … ≤ aₙ'). Think of it as "sorted from low to high, but duplicates can sit next to each other."
In-place sorting
A sort that uses only a constant amount of extra memory beyond the input array itself. In simple terms, it rearranges the data where it already lives rather than copying it into a new structure.
Comparison-based sorting
Any algorithm that determines order by comparing pairs of elements. All six algorithms in these notes (Parts 1 and 2) are comparison-based.
Stable sort
A sort that preserves the original relative order of elements with equal keys. Think of it as: if two items are "tied," a stable sort keeps them in the order they arrived.
Time complexity (Big-O)
A measure of how the number of operations grows as the input size n increases. O(n²) means the work roughly quadruples when you double n; O(n log n) means it slightly more than doubles.
You receive a sequence (a₁, a₂, …, aₙ).
You must output a permutation (a₁', a₂', …, aₙ') where a₁' ≤ a₂' ≤ … ≤ aₙ'.
Sorted data is a prerequisite for efficient searching (binary search needs it), merging, deduplication, and many other operations.
Walk through the list from left to right, comparing each pair of adjacent elements.
If the left element is larger than the right, swap them.
After one full pass, the largest unsorted element has "bubbled up" to its correct position at the end.
Repeat, each time ignoring the already-sorted tail, until a pass completes with zero swaps.
Key observations:
Each pass settles exactly one element into its final position.
A pass with no swaps means the list is fully sorted, so the algorithm can stop early.
Easy to code, but the repeated adjacent-swap work makes it slow on large inputs.
Worst case: O(n²), which occurs when the input is in reverse order.
Average case: O(n²).
Best case: O(n), when the input is already sorted (one clean pass, no swaps).
Space: O(1) extra, it sorts in place.
Treat the first element as a sorted sublist of size 1.
Take the next unsorted element (the "key") and compare it rightward-to-leftward against the sorted portion.
Shift each larger element one position to the right to make room.
Drop the key into the gap.
Repeat until every element has been inserted.
This is the same strategy most people use when sorting a hand of playing cards: pick up one card at a time and slide it into the right spot among the cards you already hold.
Worst case: O(n²), when the input is in reverse order (every new key must travel all the way to the front).
Average case: O(n²).
Best case: O(n), when the input is already sorted (each key is already in place, so no shifts happen).
Space: O(1) extra.
The O(n) best case is InsertionSort's main advantage over SelectionSort and BubbleSort. If your data is "almost sorted," InsertionSort can be surprisingly fast.
Scan the entire unsorted portion to find the minimum element.
Swap it with the first element of the unsorted portion.
The sorted section at the front grows by one.
Repeat until the unsorted portion is empty.
The distinctive feature is that each element is moved at most once (one swap per round), which minimises write operations.
Worst case: O(n²).
Average case: O(n²).
Best case: O(n²). SelectionSort always does the same number of comparisons regardless of input order, so there is no "lucky" input.
Space: O(1) extra.
Algorithm | Best Case | Average Case | Worst Case | Space | Stable? |
|---|---|---|---|---|---|
BubbleSort | O(n) | O(n²) | O(n²) | O(1) | Yes |
InsertionSort | O(n) | O(n²) | O(n²) | O(1) | Yes |
SelectionSort | O(n²) | O(n²) | O(n²) | O(1) | No |
InsertionSort is used inside production-grade hybrid sorts (such as Timsort, which Python and Java use) for small subarrays, because its low overhead beats the fancier O(n log n) algorithms when n is tiny (typically n < 16 or so). SelectionSort sees occasional use in embedded systems where minimising the number of memory writes matters more than comparison count.
Students often assume BubbleSort is always O(n²). With an early-termination flag (stop when a pass has zero swaps), BubbleSort achieves O(n) on already-sorted input.
Students often believe SelectionSort has a best case better than O(n²). It does not; it always scans the full unsorted portion regardless of order.
Students sometimes confuse "in-place" with "stable." All three algorithms here are in-place, but SelectionSort is not stable because its long-range swaps can reorder equal elements.
Students sometimes think InsertionSort and SelectionSort are the same thing. InsertionSort picks the next element and finds its place in the sorted portion; SelectionSort finds the smallest remaining element and places it at the end of the sorted portion. The direction of work is essentially reversed.
⚠️ Be ready to trace through a short array (5–8 elements) step by step for any of these three algorithms. Exam questions love asking "show the state of the array after each pass."
⚠️ Know each algorithm's best, average, and worst-case complexities cold. A common exam format is a table you must fill in.
⚠️ Understand why InsertionSort's best case is O(n) while SelectionSort's is O(n²). This comes down to what each algorithm does when no work is needed: InsertionSort skips shifts, SelectionSort still scans.
⚠️ Be able to explain stability and identify which of these three algorithms is or is not stable.
True or false: BubbleSort's worst-case time complexity is O(n log n).
Fill in the blank: InsertionSort's best-case time complexity is ______.
True or false: SelectionSort performs the same number of comparisons regardless of input order.
Fill in the blank: The sorting problem requires producing a permutation in ______ order.
True or false: All three simple sorts covered here are stable.
Answers: 1) False (it is O(n²)). 2) O(n). 3) True. 4) Non-decreasing. 5) False (SelectionSort is not stable).
Q: Describe how BubbleSort determines that the list is fully sorted and can stop.
A: If a complete pass through the array produces zero swaps, every adjacent pair is already in order, so the list is sorted. The algorithm terminates at that point.
Q: Why is InsertionSort preferred over BubbleSort and SelectionSort for nearly sorted data?
A: On nearly sorted input, most elements are already close to their correct positions. InsertionSort's inner loop only shifts elements that are out of place, so it runs in close to O(n) time. BubbleSort can also benefit from early termination, but InsertionSort typically performs fewer total operations. SelectionSort gains no advantage at all because it always scans the full unsorted portion.
Q: An exam question gives you an array in reverse-sorted order. Which of the three simple sorts will perform the most swaps, and why?
A: BubbleSort will perform the most swaps. Every adjacent pair is out of order on every pass, producing roughly n(n−1)/2 swaps in total. InsertionSort performs shifts rather than swaps, and SelectionSort performs exactly n−1 swaps (one per round) regardless of input.
Q: Is SelectionSort stable? Explain with a brief example.
A: No. Consider the array [3a, 3b, 1] where 3a and 3b are equal values. In the first round, SelectionSort swaps 3a with 1, producing [1, 3b, 3a]. The original order of the two 3s has been reversed.
Q: State the formal definition of the sorting problem.
A: Given an input sequence (a₁, a₂, …, aₙ), produce a permutation (a₁', a₂', …, aₙ') such that a₁' ≤ a₂' ≤ … ≤ aₙ'.
This material connects directly to the efficient sorts in Part 2 (HeapSort, MergeSort, QuickSort), which solve the same problem in O(n log n) time by using more sophisticated strategies. Understanding why simple sorts are O(n²) makes the divide-and-conquer speedup much more intuitive.
The concept of in-place versus extra-space trade-offs reappears throughout data structures and algorithms, particularly when you study hash tables, trees, and graph algorithms.
sorting problem, comparison sort, adjacent swap, bubble sort, insertion sort, selection sort, quadratic sort, O(n²), in-place sort, stable sort, unstable sort, best case O(n), array permutation, non-decreasing order, playing-card analogy, embedded systems sort, Timsort subroutine, CS 101 sorting, UCF Computer Science I