CPKit
v1.6.1

Merge Sort

SortingMedium

Divide the array into halves, sort them recursively, and merge them.

Alt+Shift+M

Configuration Panel

Recursive Divide & Merge Visualizer

23
0
8
1
56
2
12
3
38
4
5
5
72
6
16
7
Step: 1 / 1

Time Complexity

O(N log N) for all cases (always executes identical recursive tree divisions)

Space Complexity

O(N) auxiliary space
Conceptual Overview

Merge Sort is a Divide-and-Conquer sorting algorithm that splits the array into two halves, recursively sorts them, and then merges the sorted halves.

Algorithm Idea

Divide the array recursively at midpoints until single-element segments remain. Merge adjacent sorted segments by comparing front elements.

Stable Sorting

Stable (retains relative order of equal elements during merges)

In-place Memory

Out-of-place (requires O(N) extra memory space)

Source: CP-Algorithms search & sorting reference