Sorting algorithm interview questions, with answers

The questions, with answers

1. 1.What are the time and space complexities of the common sorting algorithms?

   Bubble, selection and insertion sort are O(n²) on average and in the worst case, with O(1) extra space. Merge sort is O(n log n) in every case, with O(n) extra space for arrays. Quicksort is O(n log n) on average and O(n²) in the worst case, with O(log n) stack space on average. Heap sort is O(n log n) in every case with O(1) extra space.

   The best cases differ and interviewers ask about them: insertion sort is O(n) on already-sorted input, bubble sort is O(n) only if it stops early when a pass makes no swaps, and selection sort is O(n²) even on sorted input because it always scans for the minimum.

2. 2.What is a stable sort, and why does it matter?

   A sort is stable if elements that compare equal keep their original relative order. Merge sort, insertion sort and bubble sort are stable; the standard forms of quicksort, heap sort and selection sort are not. It matters whenever you sort by one key after another: sort orders by date, then stably by customer, and each customer's orders stay in date order. With an unstable sort the second pass scrambles the first.

   In practice it also matters for the library you call: Java's Collections.sort and Python's sort are stable (Timsort); C++ std::sort is not, and std::stable_sort exists for exactly this reason.

3. 3.When does quicksort degrade to O(n²), and how do you prevent it?

   Quicksort is O(n²) when the pivot repeatedly splits the array badly — one side nearly empty, the other nearly everything. With "pick the first (or last) element" as the pivot, that happens on already-sorted or reverse-sorted input, which is common real data. Prevention: choose the pivot randomly, or use median-of-three (first, middle, last). Neither removes the O(n²) worst case, they make it astronomically unlikely. Introsort, which C++ std::sort uses, goes further and switches to heap sort if recursion gets too deep, giving a true O(n log n) bound.

   import random
   
   def quicksort(a, lo, hi):          # partition() places the pivot and returns its index
       if lo >= hi:
           return
       p = partition(a, lo, hi, pivot_index=random.randint(lo, hi))
       quicksort(a, lo, p - 1)
       quicksort(a, p + 1, hi)

4. 4.Why is merge sort preferred for linked lists?

   Because merge sort only ever reads elements sequentially, which is the one thing a linked list does well. Quicksort and heap sort depend on O(1) random access to jump to a pivot or a child index, and a list makes every jump O(n). Merge sort on a list also needs no extra array: you split the list by finding the middle with slow and fast pointers, sort each half, and merge by relinking nodes — O(n log n) time with O(1) extra space apart from the recursion stack, whereas the array version needs O(n) temporary space.

5. 5.Can you sort faster than O(n log n)?

   Not by comparing elements: any comparison-based sort needs Ω(n log n) comparisons in the worst case, because n elements have n! orderings and each comparison can only halve the possibilities — log₂(n!) is about n log n. You can beat it by not comparing: counting sort runs in O(n + k) when keys are integers in a range of size k, radix sort in O(d · (n + k)) for d-digit keys, and bucket sort in expected O(n) for uniformly distributed data. The catch is the assumption about the keys; with arbitrary comparable objects you're back to n log n.

6. 6.Which sorting algorithms are in-place?

   In-place means O(1) — or at most O(log n) — extra memory beyond the input. Bubble, selection, insertion and heap sort are in-place. Quicksort is usually called in-place because it partitions within the array, though its recursion stack is O(log n) on average and O(n) in the degenerate case. Merge sort on arrays is not in-place: the merge step needs a temporary array of size n. In-place merge sort exists but is complicated and slow enough that nobody uses it.

7. 7.What is the difference between best, average and worst case, and which one should you quote?

   Best case is the input that makes the algorithm fastest, worst case the input that makes it slowest, average case the expected cost over all inputs. Quote the worst case unless asked otherwise — it is the guarantee. Then add the average if it differs meaningfully, which is the whole story of quicksort: O(n²) worst, O(n log n) average, and fast in practice because of cache behaviour and low constants. Quoting only the best case ("insertion sort is O(n)") is the mistake interviewers listen for.

8. 8.Which algorithm does your language's built-in sort use?

   Python's sorted and list.sort use Timsort, a merge/insertion hybrid that is stable and O(n log n), with O(n) best case on already-sorted runs. Java uses Timsort for objects (stable) and a dual-pivot quicksort for primitive arrays (unstable, but stability is meaningless for primitives). C++ std::sort is introsort — quicksort with heap sort fallback, plus insertion sort for tiny ranges — and is not stable; std::stable_sort is a merge sort. V8 (Chrome and Node.js) has used Timsort since 2018. The reason to know this: it lets you say "I'd use the library sort; here's what it costs and whether it's stable".

How the diagnostic asks it

One question from the DSA bank, exactly as a sitting would show it. The bank has 3 on sorting algorithms & complexity and 30 across DSA.