Skip to content
Hello Python
Algorithm1 Practice2 Interview

Merge Sort

Recursively sort halves and merge them in stable O(n log n) time with auxiliary storage. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Merge Sort when the prompt's constraints and required operations match this shape: Recursively sort halves and merge them in stable O(n log n) time with auxiliary storage.

Pybit demonstrates Merge Sort in a professional Python interview workspace.
On this page · Split Until Single Items

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Merge Sort Code Labs

Split Until Single Items

Merge sort recursively divides a range until each run has length zero or one, which is already sorted. Balanced splitting creates logarithmic recursion depth.

Merge Two Sorted Contracts

Given two sorted runs, repeatedly take the smaller front. When one run empties, append the remaining suffix of the other; no later comparison can change its order.

Trace One Merge Pass

Reference
def merge_pass(values,width):
    result=[]
    for start in range(0,len(values),2*width):
        left=values[start:start+width];right=values[start+width:start+2*width];i=j=0
        while i<len(left) and j<len(right):
            if left[i]<=right[j]:result.append(left[i]);i+=1
            else:result.append(right[j]);j+=1
        result.extend(left[i:]);result.extend(right[j:])
    return result
Practice

Implement merge_pass(values,width). Merge adjacent sorted runs of width and return the new list.

Public tests

  • Merge every adjacent run pair

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Preserve Stability on Equality

Take from the left run when keys compare equal. That preserves original relative order across the split and makes merge sort stable.

Stable Merge Sort Records

Reference
def stable_merge_sort(records):
    if len(records)<2:return [item.copy() for item in records]
    mid=len(records)//2;left=stable_merge_sort(records[:mid]);right=stable_merge_sort(records[mid:]);result=[];i=j=0
    while i<len(left) and j<len(right):
        if left[i][0]<=right[j][0]:result.append(left[i]);i+=1
        else:result.append(right[j]);j+=1
    return result+left[i:]+right[j:]
Practice

Implement stable_merge_sort(records). Sort [key,label] records by key while preserving labels with equal keys.

Public tests

  • Take left first on equal keys

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Count Time and Auxiliary Space

The recurrence is two half-size sorts plus linear merging, yielding O(n log n). Standard list implementations use O(n) auxiliary merge storage and O(log n) call stack; Python slicing adds copies unless ranges are passed by index.

Explain It in an Interview

Say: “Each recursive call returns a sorted run. The merge chooses the smallest remaining front and takes left on equality for stability.” State base case, recurrence, copying policy, and why worst-case time remains O(n log n).

Python Version Note

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Merge Sort complete workflowO(n + m)O(n + m)Two already ordered runs can be combined in one pass by selecting the smaller current front. The output is sorted and contains exactly the consumed prefixes; the two pointers identify the smallest unconsumed candidates.

Space

O(n + m) for the focused Merge Two Ordered Runs implementation.

Assumptions

  • At each step the smaller pointed value is the smallest remaining value overall, so appending it preserves sorted order. When one input ends, appending the other suffix preserves order and includes every value exactly once.
  • The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

  1. State the precise Merge Sort invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. The resolved region satisfies the target ordering relation.
  3. The unresolved region still contains every item not yet placed.
  4. Two already ordered runs can be combined in one pass by selecting the smaller current front. Preserve this claim after every transition.
  5. The output is sorted and contains exactly the consumed prefixes; the two pointers identify the smallest unconsumed candidates. Preserve this claim after every transition.

When To Use Or Avoid Merge Sort

Use It When

  • Use Merge Sort when this precondition is stated or can be proved: The comparison, key domain, stability need, and memory constraints match the selected ordering method.
  • Use it when this maintained state removes repeated work: The resolved region satisfies the target ordering relation.

Choose Another Tool When

  • Avoid Merge Sort when this precondition is absent: The comparison, key domain, stability need, and memory constraints match the selected ordering method.
  • Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: The comparison, key domain, stability need, and memory constraints match the selected ordering method.

Avoid

def merge_ordered_runs(left, right):
    pass

Use instead

def merge_ordered_runs(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
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

Where you will hit this: Merge Two Ordered Runs(opens in a new tab)

Breaking the state transition

Stops after the shared scan and drops the unconsumed suffix from whichever ordered run remains.

Prevent it: Preserve this proof obligation: The resolved prefix, suffix, rank, digit pass, or bucket remains in its documented final relation.

Avoid

def merge_ordered_runs(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
    return merged

Use instead

def merge_ordered_runs(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
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

Where you will hit this: Merge Two Ordered Runs(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(n + m).

Avoid

def merge_ordered_runs(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
    return merged

Use instead

def merge_ordered_runs(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
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

Where you will hit this: Sort an Array(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.