⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#912) before relying on it.

Merge Sort

An interactive visualization of the merge sort divide-and-conquer algorithm. Watch how the array is recursively split into halves and then merged back together in sorted order.

Divide and Conquer LeetCode 912 ↗ Medium

The Problem

Given an array of integers nums, sort the array in ascending order and return it.

You must solve the problem without using any built-in functions in O(n log n) time complexity and with the smallest space complexity possible.

Interactive Visualization

Array (comma-separated)

Preset

Speed:

Merge Sort Tree

Code

fun mergeSort(arr: List<Int>): List<Int> {    if (arr.size <= 1) {        return arr    }    val mid = arr.size / 2    val left = mergeSort(arr.subList(0, mid))    val right = mergeSort(arr.subList(mid, arr.size))    return merge(left, right)}fun merge(left: List<Int>, right: List<Int>): List<Int> {    val result = mutableListOf<Int>()    var i = 0; var j = 0    while (i < left.size && j < right.size) {        if (left[i] <= right[j]) {            result.add(left[i])            i++        } else {            result.add(right[j])            j++        }    }    result.addAll(left.subList(i, left.size))    result.addAll(right.subList(j, right.size))    return result}

def mergeSort(arr):    if len(arr) <= 1:        return arr    mid = len(arr) // 2    left = mergeSort(arr[:mid])    right = mergeSort(arr[mid:])    return merge(left, right)def merge(left, right):    result = []    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

Status

Press Step or Play to begin.

How It Works

Key Insight

Merge Sort follows the divide and conquer paradigm: divide the array into two halves, conquer by recursively sorting each half, then combine the two sorted halves by merging them together. The merging step is efficient because both halves are already sorted, so we just need to compare the front elements and pick the smaller one.

The Algorithm

Base case: An array of length 0 or 1 is already sorted; return it directly.
Divide: Find the midpoint mid = len(arr) // 2 and split the array into arr[:mid] and arr[mid:].
Conquer: Recursively sort the left half and the right half.
Combine: Merge the two sorted halves. Use two pointers i and j to walk through the left and right halves, always picking the smaller element.
Remaining elements: After one half is exhausted, append the remaining elements from the other half.

Complexity

Time O(n log n)

Space O(n)

The array is split into log n levels, and at each level we do O(n) work to merge all subarrays. The extra space comes from the temporary arrays created during merging. Merge Sort is a stable sort and guarantees O(n log n) performance regardless of the input order.