Algorithms
Sorting (Elementary)
Difficulty: Beginner
Insertion sort is O(n^2) and quick sort is O(n log n), yet V8 actually runs insertion sort on arrays shorter than ten elements because the constant factors are smaller. The takeaway is that elementary sorts are not just historical...
Sorting (Elementary)
Insertion sort is O(n^2) and quick sort is O(n log n), yet V8 actually runs insertion sort on arrays shorter than ten elements because the constant factors are smaller. The takeaway is that elementary sorts are not just historical curiosities; they are the algorithms that real engines drop down to once an array is small enough.
Sorting (Elementary) walks through bubble sort, selection sort, and insertion sort in detail. For each, you will trace the pass-by-pass behavior on a small input, count comparisons and swaps, and analyze worst, best, and average time complexity. Along the way the lesson introduces the vocabulary that every later sorting topic relies on: passes, the growing sorted region, the loop invariant that proves correctness, in-place vs. extra-space sorts, and stability (whether equal keys keep their original relative order).
In Arrays & Strings, you learned how arrays store and index data; sorting is the first time you will rearrange that storage in place. Iteration Patterns on Arrays/Strings trained you in nested loops and swaps, and these three sorts are essentially structured nested loops with a clear invariant.
Up next, Searching (Basics) establishes the linear-search baseline whose O(n) cost is exactly what binary search will later cut down once your data is sorted.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain how Bubble Sort, Selection Sort, and Insertion Sort each work using passes, comparisons, and swaps.
Implement all three elementary sorts correctly in both JavaScript and Python.
Trace each algorithm step-by-step on a small input and predict the array state after each pass.
Analyze the time complexity (best, worst, average) and space complexity of each algorithm.
Define sorting stability and classify each elementary sort as stable or unstable.
Choose the appropriate elementary sort for a given scenario based on input characteristics.
Why This Matters
01
Elementary sorts introduce the core vocabulary of sorting: comparisons, swaps, passes, sorted regions, and invariants. These concepts recur in every sorting algorithm you will ever learn.
02
Understanding why O(n^2) sorts are slow motivates the need for O(n log n) algorithms like Merge Sort and Quick Sort.
03
Insertion Sort is not just a teaching tool — it is the algorithm of choice for small arrays and nearly-sorted data, and it powers the inner loop of Timsort (Python) and V8 sort (JavaScript).
04
Sorting enables other algorithms: binary search requires sorted input, and many greedy strategies begin with a sort step.
Key Terms
7 terms you'll encounter in this lesson
Comparison-based sort
A sorting algorithm that determines order by comparing pairs of elements. All elementary sorts (bubble, selection, insertion) are comparison-based.
Pass
One full sweep through the array (or the unsorted portion of it). After each pass, at least one more element is in its final position.
Swap
Exchanging two elements in the array to move them toward their correct positions.
Invariant
A property that remains true throughout the algorithm. For example, in Insertion Sort, all elements to the left of the current index are always sorted relative to each other.
Stable sort
A sorting algorithm that preserves the relative order of elements with equal keys. Bubble Sort and Insertion Sort are stable; Selection Sort is not.
In-place sort
A sorting algorithm that uses only O(1) extra memory beyond the input array. All three elementary sorts are in-place.
Adaptive sort
A sorting algorithm whose performance improves when the input is already partially sorted. Insertion Sort is adaptive (O(n) on sorted input); Selection Sort is not.
Related Problems
Coding problems that put this lesson's concepts into practice
Heads Up
Common misconceptions to watch out for
"All O(n^2) sorts perform the same in practice"
Insertion Sort is significantly faster on nearly-sorted data (O(n) best case), while Selection Sort always does O(n^2) comparisons regardless of input order. The constant factors and cache behavior also differ.
"Selection Sort is stable because it doesn't do many swaps"
Selection Sort is unstable. When it finds the minimum and swaps it to the front, it can jump an equal element over another. For example, sorting [2a, 2b, 1] moves 1 to front by swapping with 2a, producing [1, 2b, 2a] — the relative order of the two 2s is reversed.
"Bubble Sort always needs n-1 passes"
With the early-exit optimization (stop when a pass makes zero swaps), Bubble Sort can finish in as few as 1 pass on already-sorted input, achieving O(n) best-case time.
"Insertion Sort shifts elements using swaps"
The standard Insertion Sort uses shifts (moving elements one position right) rather than repeated swaps. This is more efficient because a shift is a single write, while a swap requires three operations (temp, write, write).