Data Structures & Algorithms Hashing & Sorting Syllabus

Describe the Insertion Sort process.

Build the sorted portion one element at a time: take the next element and shift larger sorted elements right until the correct insertion point is found, then place it there.

State the best, average, and worst-case complexity of Insertion Sort.

Best $O(n)$ (nearly sorted input), average and worst $O(n^{2})$. Space $O(1)$; it is stable, in-place, and efficient for small or nearly sorted arrays.

What does it mean for a sorting algorithm to be stable?

A sort is stable if it preserves the relative order of elements that compare equal (equal keys keep their original input order).

Classify these sorts as stable or unstable: Bubble, Insertion, Merge, Selection, Quick, Heap.

Stable: Bubble, Insertion, Merge (standard). Unstable (standard implementations): Selection, Quick, Heap.

Why does stability matter in practice?

When sorting by a secondary key after a primary key, stability preserves the earlier ordering, enabling correct multi-key (radix-style) sorting and consistent tie-breaking.

Describe the Merge Sort algorithm.

A divide-and-conquer sort: recursively split the array in half, sort each half, then merge the two sorted halves into one sorted array by repeatedly taking the smaller front element.

State the time and space complexity of Merge Sort.

$O(n \log n)$ time in best, average, and worst cases. Auxiliary space $O(n)$ for the merge buffer (array version). It is stable but not in-place.

Give the recurrence relation for Merge Sort and its solution.

$T(n) = 2T\!\left(\frac{n}{2}\right) + O(n)$, which by the Master Theorem solves to $T(n) = O(n \log n)$.

Describe the Quick Sort algorithm.

Divide-and-conquer: choose a pivot, partition the array so smaller elements go left and larger go right of the pivot, then recursively sort the two partitions. The pivot ends in its final position.

State the best, average, and worst-case time complexity of Quick Sort.

Best and average $O(n \log n)$; worst $O(n^{2})$ (e.g. already-sorted input with a poor pivot). Average space $O(\log n)$ for recursion; in-place, generally unstable.

How can Quick Sort's worst case be avoided?

Use randomized pivot selection or the median-of-three rule, making the $O(n^{2})$ case extremely unlikely and giving expected $O(n \log n)$ performance.

Give the worst-case recurrence for Quick Sort with a maximally unbalanced pivot.

$T(n) = T(n-1) + O(n)$, which solves to $T(n) = O(n^{2})$.

Describe the Heap Sort algorithm.

Build a max-heap from the array, then repeatedly swap the root (maximum) with the last element, shrink the heap, and sift the new root down. This extracts elements in sorted order.

State the time and space complexity of Heap Sort.

$O(n \log n)$ in best, average, and worst cases. In-place with $O(1)$ auxiliary space, but not stable.

What is the time complexity of building a heap from an unsorted array?

$O(n)$ using the bottom-up heapify (sift-down) construction — tighter than the naive $O(n \log n)$ of repeated insertions.

For a 0-indexed binary heap array, give the index formulas for a node at index $i$.

Left child $2i+1$, right child $2i+2$, parent $\left\lfloor \frac{i-1}{2} \right\rfloor$.

State the lower bound for comparison-based sorting and its justification.

Any comparison sort requires $\Omega(n \log n)$ comparisons in the worst case. A decision tree with $n!$ leaves has height $\geq \log_2(n!) = \Theta(n \log n)$ by Stirling's approximation.

Why can Counting, Radix, and Bucket sorts beat the $\Omega(n \log n)$ bound?

They are not comparison-based; they use the values themselves (as indices/digits/ranges) rather than pairwise comparisons, so the decision-tree lower bound does not apply.

Describe the Counting Sort algorithm.

Count the occurrences of each key value in a range $[0,k]$, compute prefix sums to find output positions, then place each element into its sorted position using the counts.

State the time and space complexity of Counting Sort.

Time $O(n + k)$ and space $O(n + k)$, where $k$ is the range of key values. It is stable and efficient only when $k = O(n)$.

Describe the Radix Sort algorithm (LSD variant).

Sort the numbers digit by digit from least significant to most significant, using a stable sort (typically counting sort) on each digit. After processing all digits the array is fully sorted.

State the time complexity of Radix Sort.

$O(d\,(n + b))$, where $d$ is the number of digits and $b$ is the base/radix. For fixed-width integers this is effectively $O(n)$.

Why must the per-digit sort used inside Radix Sort be stable?

Stability preserves the ordering established by less significant digits when sorting on more significant digits; without it, LSD radix sort produces incorrect results.

Describe the Bucket Sort algorithm.

Distribute the $n$ elements into $k$ buckets by value range, sort each bucket individually (often with insertion sort), then concatenate the buckets in order.

State the average and worst-case complexity of Bucket Sort.

Average $O(n + k)$ when inputs are uniformly distributed across buckets; worst case $O(n^{2})$ when all elements fall into one bucket. Space $O(n + k)$.

Describe Linear Search and its complexity.

Scan elements sequentially from start until the target is found or the list ends. Time $O(n)$ worst/average, $O(1)$ best; space $O(1)$. Works on unsorted data.

Describe the Binary Search algorithm and its precondition.

On a sorted array, repeatedly compare the target to the middle element and discard the half that cannot contain it, halving the search space each step. Precondition: the array must be sorted.

State the time complexity of Binary Search and its recurrence.

$O(\log n)$ time. Recurrence $T(n) = T\!\left(\frac{n}{2}\right) + O(1)$, solving to $T(n) = O(\log n)$. Space $O(1)$ iterative, $O(\log n)$ recursive.

Give a numerically safe formula for the midpoint in Binary Search and explain why.

$\text{mid} = \text{low} + \frac{\text{high} - \text{low}}{2}$. This avoids the integer overflow that $\frac{\text{low}+\text{high}}{2}$ can cause for large indices.

Describe Ternary Search and its complexity.

Split the range into three parts using two midpoints $m_1, m_2$ and discard two-thirds each step (on a sorted array, or to find the extremum of a unimodal function). Time $O(\log_3 n) = O(\log n)$.

Why is Binary Search generally preferred over Ternary Search despite both being $O(\log n)$?

Ternary search does more comparisons per level ($\log_3 n$ levels but up to $2$ comparisons each, $\approx 2\log_3 n \approx 1.26\log_2 n$), so binary search performs fewer total comparisons.