Pattern visualizer
Merge Sort
A single element is trivially 'sorted', so recursively split the array in half until every piece is down to one element — that's the free part. All the real work happens on the way back up: merge two already-sorted halves by repeatedly comparing their fronts and taking the smaller, then appending whatever's left. Because merging two sorted lists is O(n), and there are O(log n) levels of splitting, the whole sort is O(n log n). Animated on: arr = [38,27,43,3,9,82,10] — sort the array..
Divide into singles, then merge back sorted
time O(n log n)space O(n)step 1 / 10
38
[0]27
[1]43
[2]3
[3]9
[4]82
[5]10
[6]line 3
Start with the whole array. Recursively split it in half until every subarray holds a single element.
Pseudocode
1FUNCTION mergeSort(arr):2 IF the length of arr is 1 or less: RETURN arr3 mid = the length of arr divided by 24 left = mergeSort(the first half of arr)5 right = mergeSort(the second half of arr)6 RETURN merge(left, right)7FUNCTION merge(left, right):8 compare the fronts of left and right, take the smaller, repeat9 append whatever elements are left over10 RETURN the merged array
← / → step · space play · Home restart