Merge Sort Visualizer

How it works

1. If the range A[lo..hi] has 0 or 1 elements, it is already sorted — return.
2. Split it at mid = ⌊(lo + hi) / 2⌋.
3. Recursively sort the left half A[lo..mid].
4. Recursively sort the right half A[mid + 1..hi].
5. Merge: copy the halves out as L and R, repeatedly write the smaller of L[i] and R[j] back into A[k] (taking from L on ties), then copy whatever is left over.

Worked example: sorting [38, 27, 43, 3, 9, 82, 10]

The visualizer above opens on this array and draws the recursion as a tree of boxes:

• Split at mid = 3 into [38, 27, 43, 3] and [9, 82, 10], and keep halving until every piece is a single element.
• Merge pairs: [38] + [27] → [27, 38], [43] + [3] → [3, 43], [9] + [82] → [9, 82].
• Merge runs: [27, 38] + [3, 43] → [3, 27, 38, 43] and [9, 82] + [10] → [9, 10, 82].
• Final merge: 3 vs 9 takes 3, 27 vs 9 takes 9, 27 vs 10 takes 10, then 27, 38 and 43 each beat 82, and the leftover 82 is copied: [3, 9, 10, 27, 38, 43, 82].

In total 14 comparisons and 20 writes. Each element is written once for every merge it takes part in — three times for most of them, twice for 10, which became a single-element piece one level sooner.

Why merge sort is O(n log n) in every case

Halving again and again gives a recursion tree with ⌈log₂ n⌉ levels. On each level the merges together touch every element once, which is O(n) work per level. Multiply the two: O(n log n). As a recurrence, T(n) = 2T(n/2) + O(n), which solves to Θ(n log n).

The split never looks at the values, so there is no bad input: sorted, reversed and random arrays all take Θ(n log n) time. Only the comparison count varies a little, because a merge stops comparing as soon as one run is used up. For n = 1,000 that is about 10,000 element moves, where insertion sort could need up to 500,000.

The merge step and stability

Merging two sorted runs is the heart of the algorithm. Keep a pointer at the front of each run: the smaller of the two front elements is the smallest one remaining overall, so it goes next. Every comparison outputs one element, so merging runs with m elements in total takes at most m − 1 comparisons.

On a tie the code takes from the left run (L[i] <= R[j]). The left run came earlier in the input, so equal elements keep their original order — that is what makes merge sort stable. Write < instead and it quietly stops being stable.

Merge sort vs quick sort

• Worst case: merge sort is always O(n log n); quick sort is O(n²) with consistently bad pivots.
• Memory: merge sort needs an O(n) buffer for arrays; quick sort sorts in place with an O(log n) stack.
• Stability: merge sort is stable; quick sort is not.
• Speed on arrays in RAM: quick sort is usually faster, thanks to its tight, cache-friendly partition loop.
• Linked lists and huge files: merge sort wins. It reads runs sequentially, so it merges linked lists with O(1) extra space and sorts files far larger than memory (external merge sort).

That is why stable library sorts are merge-based: Python's sorted(), Java's object sort and V8's Array.prototype.sort use Timsort, and C++ offers std::stable_sort.

Common mistakes and interview tips

• Computing mid = (lo + hi) / 2 with fixed-size integers can overflow on huge arrays; lo + (hi − lo) / 2 is safe.
• Forgetting to copy the leftovers once one run is exhausted.
• Allocating new arrays in every call. It works, but one buffer allocated up front is much faster.
• Classic follow-ups: count inversions in O(n log n) (add the number of elements left in L whenever you take from R), merge k sorted lists with a heap, and sort a linked list in O(n log n).

Time and space complexity

Merge Sort in Python

def merge_sort(A, lo=0, hi=None):
    # Sorts A[lo..hi] (inclusive) in place. Stable.
    # O(n log n) time in every case, O(n) extra space.
    if hi is None:
        hi = len(A) - 1
    if lo >= hi:                        # 0 or 1 element
        return
    mid = (lo + hi) // 2
    merge_sort(A, lo, mid)              # sort left half
    merge_sort(A, mid + 1, hi)          # sort right half
    merge(A, lo, mid, hi)


def merge(A, lo, mid, hi):
    L = A[lo:mid + 1]                   # copies of the two sorted runs
    R = A[mid + 1:hi + 1]
    i = j = 0
    k = lo
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:                # <= keeps it stable
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        k += 1
    while i < len(L):                   # leftovers (only one loop runs)
        A[k] = L[i]
        i += 1
        k += 1
    while j < len(R):
        A[k] = R[j]
        j += 1
        k += 1

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• Quick Sort VisualizerQuick sort picks a pivot, moves smaller values left and larger ones right, then recurses: O(n log n) on average. Watch Lomuto and Hoare partitioning animated.
• Insertion Sort VisualizerInsertion sort takes each element and slides it left into place in the sorted prefix. Watch every shift animated, with Python code and O(n²) complexity.
• Counting Sort VisualizerCounting sort sorts integers in O(n + k) time by counting each value and placing elements with prefix sums, with no comparisons. Watch every phase animated.
• Linked List VisualizerInteractive linked list visualizer: watch every pointer change as you insert, delete, search and reverse singly, doubly and circular lists, with code and costs.
• Sorting Algorithm VisualizerSorting algorithm visualizer: watch bubble, selection, insertion, shell, counting, radix, merge and quick sort step by step, then race them in Compare mode.