Sorting — Chapter Quiz · Data Structures & Algorithms

Quiz

Sorting — Chapter Quiz

Eight questions on stability, in-place sorts, comparison vs non-comparison sorts, the Ω(n log n) lower bound, and JS TimSort.

0/ 9

Question 1
1
What does it mean for a sorting algorithm to be 'stable'?
AIt always runs in O(n log n) timeBEqual elements retain their original relative order in the sorted outputCIt uses O(1) extra spaceDIt performs the same number of comparisons on every input
Stability matters when records have multiple fields. If you sort employees by department (stable), employees within the same department remain in their prior order. Merge sort is stable; quick sort is typically not.
Question 2
2
What is a gotcha with JavaScript's built-in Array.prototype.sort() when sorting numbers?
AIt only works on arrays with fewer than 100 elementsBWithout a comparator it converts elements to strings and sorts lexicographically, so [10, 9, 2] sorts to [10, 2, 9]CIt always sorts in descending orderDIt mutates a copy of the array, not the original
[10, 9, 2].sort() yields [10, 2, 9] because "10" < "2" lexicographically. Always provide a numeric comparator: .sort((a, b) => a - b).
Question 3
3
What sorting algorithm does V8 use for Array.prototype.sort()?
AQuick sortBHeap sortCTimSort (a hybrid of merge sort and insertion sort)DRadix sort
V8 has used TimSort since Node.js 11 (V8 7.0). TimSort is stable, adaptive (fast on nearly-sorted data), and O(n log n) worst case. It detects natural runs and merges them efficiently.
Question 4
4
What is the theoretical lower bound for comparison-based sorting algorithms?
AΩ(n)BΩ(n log n)CΩ(n²)DΩ(log n)
Any comparison-based sort must distinguish among n! possible orderings. A binary decision tree needs at least log₂(n!) ≈ n log n levels. No comparison sort can do better than Ω(n log n) in the worst case.
Question 5
5
Which of the following sorting algorithms is NOT comparison-based and can beat the Ω(n log n) bound?
AMerge sortBHeap sortCCounting sortDQuick sort
Counting sort (and radix sort, bucket sort) exploit the structure of integer keys. Counting sort runs in O(n + k) where k is the key range — faster than O(n log n) when k = O(n).
Question 6
6
Quick sort is always faster than merge sort in practice.
TTrueFFalse
Quick sort has O(n²) worst-case (e.g., sorted input with a bad pivot). Merge sort guarantees O(n log n). In practice, quick sort often wins due to cache locality, but it depends heavily on the pivot strategy and input distribution.
Question 7
7
Heap sort is an in-place, O(n log n) sort that uses a data structure called a ___.
Heap sort first builds a max-heap in O(n), then repeatedly extracts the maximum (O(log n) sift-down) to sort in place. It is not stable but uses only O(1) extra space.
Question 8
8
Which sorting algorithms are stable? (Select all that apply)
Select all that apply.
AMerge sortBInsertion sortCHeap sortDCounting sort (with careful implementation)
Merge sort and insertion sort preserve equal-element order. Counting sort is stable when implemented by iterating the input in reverse and filling positions from the right. Heap sort is NOT stable — sifting can reorder equal elements.

Test what you learned.