How Do You Choose Between Checking, Bubble Sort, and Merge Sort?
Checking order is linear, bubble sort is quadratic, and merge sort is linearithmic. The task contract determines which operation is needed.
“Is this ordered?” and “put this in order” are different problems. A sortedness check stops at the first descent. Bubble sort demonstrates local swaps. Merge sort is the scalable general-purpose algorithm taught in this course.
Three contracts
A non-decreasing array permits equal neighbours. The invariant for a check is that the prefix through the current index is ordered; one descent proves the whole array is not.
Bubble sort copies the input, repeatedly swaps adjacent inversions, and may stop after a pass with no swaps. After each full pass, the largest unsettled value is in its final suffix position. Its worst-case time is O(n²), with O(n) space here because the input is preserved.
Merge sort recursively sorts two halves and linearly merges their sorted runs. Its recurrence is T(n) = 2T(n / 2) + O(n), yielding O(n log n) time and O(n) auxiliary array space.
Worked choice
For [1, 2, 2], an order check performs two comparisons and returns true. Sorting it again does unnecessary work. For [3, 2, 1], bubble sort exposes three inversions through swaps; merge sort reaches the same result with the stronger asymptotic guarantee.
TypeScript and edge cases
values.slice()makes a shallow copy before an in-place teaching sort.- JavaScript's default
.sort()compares string forms; numeric sorting needs(a, b) => a - b. - Empty and one-value arrays are already sorted.
- Stability means equal-key records retain input order. Merge from the left on equality to preserve it.
- An early-exit bubble sort has O(n) best-case time but remains O(n²) worst-case.
- Do not call the built-in sort when the exercise is assessing the algorithm.
Optional enrichment
Compare merge sort with quicksort on stability, worst-case time, and auxiliary storage. No one comparison sort is best on every axis.