Skip to content
Merge sort

Merge sort.

Time (worst)
O(n log n)
Space
O(n)

Split into small groups. Join them back in order.

Why learn merge sort?

Merge sort splits a list into smaller groups until each has one number. Then it joins them in order: compare the first number left in each group and take the smaller one. Repeat until the whole list is sorted. Its predictable O(n log n) time makes it useful for larger lists, but it needs extra memory.

Customize input

Smallest → biggest

0 comparisons

Start

Let’s put these numbers in order

A small list is easier to sort than a big one. Break this list into smaller groups. Then put the groups back together, taking the smaller number each time.

1. Make smaller groups→2. Put them back in order
Split the array down into smaller groups. Keep every group visible.
Original array
6
3
8
2

Use Next for one action, or Play to watch. Drag the timeline to preview silently.

Voice is unavailable in this browser. Follow the explanations above.

Where does this group fit?

This is the whole list.

Review the split and merge outline

Split [6, 3, 8, 2] into [6, 3] and [8, 2]

Split [6, 3] into [6] and [3]

Split [8, 2] into [8] and [2]

Join → [3, 6]

Join → [2, 8]

Join → [2, 3, 6, 8]

About log n levels of splitting; about n numbers processed when joining each level. Together: O(n log n).

Follow the logic

Python

This overview shows all splits first, then joins from the left upward. The Python function finishes each left half before working on its right half. In Python, i and j mark the next number available in the left and right groups. The row above them is result. Moving tiles represents copying values into that new list.

def merge_sort(a):    if len(a) <= 1:        return a    mid = len(a) // 2    left = merge_sort(a[:mid])    right = merge_sort(a[mid:])    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

n is the number of items. Best, average, and worst-case time: O(n log n). Each split roughly halves a group, and joining each level processes all its numbers. Auxiliary space: O(n), plus O(log n) call depth. Equal values keep their original order because ties are taken from the left first. Playback snapshots use additional memory. Comparisons count checks between values; placements count values added to merged lists.