DSA Visual

Merge Sort

Explore merge sort's divide-and-conquer approach - split, sort, and merge arrays visually.

Time O(n log n) · Space O(n) · Stable

Merge Sort Animation

–

Waiting for input...

5
2
8
1
4
3
10
5
2
8
1
4
3
10
5
2
8
1
4
3
10
2
8
1
4
3
10
5
↓ Divide↑ Merge

Color: Compare • Insert/Merged • Processing subarray

Implementation

Python
def merge_sort_top_down_recursion(arr, depth=0):
    if arr is None or len(arr) == 0:
        raise ValueError("Array is empty")
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort_top_down_recursion(arr[:mid], depth + 1)
    right = merge_sort_top_down_recursion(arr[mid:], depth + 1)

    merged = []
    l, r = 0, 0
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            merged.append(left[l])
            l += 1
        else:
            merged.append(right[r])
            r += 1

    while l < len(left):
        merged.append(left[l])
        l += 1

    while r < len(right):
        merged.append(right[r])
        r += 1

    return merged
About Merge Sort

How Merge Sort Works

Merge sort is a divide-and-conquer algorithm that splits the array in half, recursively sorts each half, and then merges the sorted halves back together. It guarantees O(n log n) time in all cases, making it reliable for large datasets.

Recursively divide the array into halves until each sub-array has one element. Then merge pairs of sub-arrays by comparing their elements and placing them in order. The merge step is the key operation that combines two sorted sequences into one.

Complexity

Time
O(n log n)
Space
O(n)
Stability
stable

When to Use Merge Sort

  • Large datasets requiring guaranteed O(n log n) performance
  • Linked list sorting where random access is expensive
  • Stable sorting when relative order of equal elements matters

More in Sorting

Bubble SortO(n²)Insertion SortO(n²)Selection SortO(n²)Quick SortO(n log n)Counting SortO(n + k)