Merge Sort

·Medium·Sorting

Divide-and-conquer algorithm · recursively splits and merges

Practice mode

Try your own input

Change the array and replay the algorithm from step one.

Step

Current step

Merge Sort: Divide the array into two halves, recursively sort them, and then merge the two sorted halves.

Array workspace

Merge Sort

Step 1 / 79init

100%

[0]

[1]

[2]

[3]

[4]

[5]

[6]

step 1 / 79

Space play← → stepHome reset

TimeO(n log n)·SpaceO(n)

Merge Sort

1class Solution {
2  merge(arr, low, mid, high) {
3    let temp = [];
4    let left = low;
5    let right = mid + 1;
6 
7    while (left <= mid && right <= high) {
8      if (arr[left] <= arr[right]) {
9        temp.push(arr[left]);
10        left++;
11      } else {
12        temp.push(arr[right]);
13        right++;
14      }
15    }
16 
17    while (left <= mid) {
18      temp.push(arr[left]);
19      left++;
20    }
21 
22    while (right <= high) {
23      temp.push(arr[right]);
24      right++;
25    }
26 
27    for (let i = low; i <= high; i++) {
28      arr[i] = temp[i - low];
29    }
30  }
31 
32  mergeSortHelper(arr, low, high) {
33    if (low >= high) return;
34 
35    let mid = Math.floor((low + high) / 2);
36    this.mergeSortHelper(arr, low, mid);
37    this.mergeSortHelper(arr, mid + 1, high);
38    this.merge(arr, low, mid, high);
39  }
40 
41  mergeSort(nums) {
42    this.mergeSortHelper(nums, 0, nums.length - 1);
43    return nums;
44  }
45}

Command Palette

Merge Sort

Merge Sort