Can you write a program that implements merge sort?

What the interviewer wants to learn

  • Your ability to translate an algorithmic idea into correct, readable code.
  • Understanding of recursion, divide‑and‑conquer, and array manipulation.
  • Awareness of time and space complexity, and ability to discuss trade‑offs.
  • How you communicate technical details clearly.

How to structure your answer

1. **Clarify the requirements** – ask about input type (list/array), in‑place vs. returning a new list, and language constraints.

2. **Outline the high‑level steps** – split, sort each half recursively, then merge.

3. **Explain the merge routine** – linear pass with two pointers.

4. **State complexity** – O(n log n) time, O(n) extra space (or O(log n) recursion stack if in‑place).

5. **Write the code** – keep it clean, handle base case, and show the merge function.

6. **Walk through a tiny example** to prove correctness.

Example answer

“Sure, I’ll write a simple merge‑sort in Python that takes a list and returns a new sorted list. First, the function checks if the list has one or zero elements – that’s the base case, so it just returns the list. Otherwise I split the list in half, recursively sort each half, and then merge the two sorted halves. The merge step uses two indices to walk through the left and right sub‑lists, appending the smaller element to a result list until one side is exhausted, then it appends the remainder. The overall time complexity is O(n log n) because we do log n levels of recursion and each level processes all n elements. The extra space is O(n) for the temporary merged list, plus O(log n) for the recursion stack. Here’s the code:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

def merge(left, right):
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    # append any leftovers
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

If we run `merge_sort([5, 2, 9, 1])` we get `[1, 2, 5, 9]`.”

Mistakes to avoid

  • Jumping straight into code without confirming input expectations.
  • Forgetting the base case, which leads to infinite recursion.
  • Mixing up indices during the merge step, causing out‑of‑range errors or duplicate elements.
  • Ignoring the discussion of complexity; interviewers often probe on why merge sort is O(n log n).
  • Writing overly compact code that is hard to read; clarity matters more than clever one‑liners.

More coding questions