Merge Sort | Learn

In computer science, merge sort (also commonly spelled mergesort) is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Mergesort is a divide and conquer algorithm that was invented by John von Neumann in 1945.

An example of merge sort. First divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally all the elements are sorted and merged.

Merge Sort

A recursive merge sort algorithm used to sort an array of 7 integer values. These are the steps a human would take to emulate merge sort (top-down).

Merge Sort

Complexity

Name	Best	Average	Worst	Memory	Stable	Comments
Merge sort	$n log(n)$	$n log(n)$	$n log(n)$	$n$	Yes

Implementations

Python

1
# TODO: Implement in Python

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
console.log(`original array = [${D[0].join(', ')}]`);

function pow(base, expo) {
  let ans = 1;
  for (let i = 0; i < expo; i++) {
    ans *= base;
  }
  return ans;
}

function digit(i, exp) {
  return parseInt(D[0][i] / pow(10, exp) % 10);
}

for (let exp = 0; exp < 3; exp++) {
  
  console.log(`Digit: ${exp}`);
  
  let i;
  for (i = 0; i < D[0].length; i++) {
    const d = digit(i, exp);
    
    D[2][d] += 1;
    
  }
  for (i = 1; i < 10; i++) {
    
    D[2][i] += D[2][i - 1];
    
  }
  for (i = D[0].length - 1; i >= 0; i--) {
    const d = digit(i, exp);
    
    D[2][d] -= 1;
    
    D[1][D[2][d]] = D[0][i];
    
  }
  for (i = 0; i < D[0].length; i++) {
    
    D[0][i] = D[1][i];
    
  }
  for (i = 0; i < 10; i++) {
    D[2][i] = 0;
    
  }
}

console.log(`sorted array = [${D[0].join(', ')}]`);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
console.log(`original array = [${D[0].join(', ')}]`);

function mergeSort(start, end) {
  if (Math.abs(end - start) <= 1) return;

  let mergeFrom = 0;
  let mergeTo = 1;
  let width;
  let i;
  for (width = 1; width < end; width *= 2) {
    
    for (i = 0; i < end; i += 2 * width) {
      merge(mergeFrom, i, Math.min(i + width, end), Math.min(i + 2 * width, end), mergeTo);
    }
    // this could be copy(mergeTo, mergeFrom, start, end);
    // but it is more effecient to swap the input arrays
    // if you did copy here, you wouldn't need the copy at the end
    mergeFrom = (mergeFrom === 0 ? 1 : 0);
    mergeTo = 1 - mergeFrom;
  }
  if (mergeFrom !== 0) {
    
    copy(mergeFrom, mergeTo, start, end);
  }
}

function merge(mergeFrom, start, middle, end, mergeTo) {
  let i = start;
  let j = middle;
  let k;
  // in an actual merge implementation, mergeFrom and mergeTo would be arrays
  // here for the ability to trace what is going on better, the arrays are D[mergeFrom] and D[mergeTo]

  for (k = start; k < end; k++) {

    if (i < middle && (j >= end || D[mergeFrom][i] <= D[mergeFrom][j])) {

      D[mergeTo][k] = D[mergeFrom][i];
      i += 1;
    } else {

      D[mergeTo][k] = D[mergeFrom][j];
      j += 1;
    }
  }
}

function copy(mergeFrom, mergeTo, start, end) {
  let i;
  for (i = start; i < end; i++) {

    D[mergeTo][i] = D[mergeFrom][i];

  }
}

mergeSort(0, D[0].length);

console.log(`sorted array = [${D[0].join(', ')}]`);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
console.log(`original array = [${D.join(', ')}]`);

function mergeSort(start, end) {
  if (Math.abs(end - start) <= 1) return [];
  const middle = Math.ceil((start + end) / 2);

  mergeSort(start, middle);
  mergeSort(middle, end);

  console.log(`divide left[${start}, ${middle - 1}], right[${middle}, ${end - 1}]`);
  
  return mergeSort.merge(start, middle, end);
}

mergeSort.merge = (start, middle, end) => {
  const leftSize = middle - start;
  const rightSize = end - middle;
  const maxSize = Math.max(leftSize, rightSize);
  const size = end - start;
  const left = [];
  const right = [];
  let i;

  for (i = 0; i < maxSize; i++) {
    if (i < leftSize) {
      left.push(D[start + i]);
      
    }
    if (i < rightSize) {
      right.push(D[middle + i]);
      
    }
  }
  
  console.log(`left array = [${left.join(', ')}], ` + `right array = [${right.join(', ')}]`);

  i = 0;
  while (i < size) {
    if (left[0] && right[0]) {
      if (left[0] > right[0]) {
        D[start + i] = right.shift();
        
        console.log(`rewrite from right array[${i}] = ${D[start + i]}`);
        
      } else {
        D[start + i] = left.shift();
        
        console.log(`rewrite from left array[${i}] = ${D[start + i]}`);
        
      }
    } else if (left[0]) {
      D[start + i] = left.shift();
      
      console.log(`rewrite from left array[${i}] = ${D[start + i]}`);
      
    } else {
      D[start + i] = right.shift();
      
      console.log(`rewrite from right array[${i}] = ${D[start + i]}`);
      
    }

    i++;
  }

  const tempArray = [];
  for (i = start; i < end; i++) tempArray.push(D[i]);
  
  console.log(`merged array = [${tempArray.join(', ')}]`);
  
};

mergeSort(0, D.length);

console.log(`sorted array = [${D.join(', ')}]`);

Complexity

Implementations

JavaScript

References