Mergesort

Updated: 25 March 2024

Mergesort

One of the two classical sorting algorithms, the other is QuickSort

Mergesort is the basic sort in lots of different languages

Algorithm

• Divide an array into two halfs
• Recursively sort each half
• Merge the two halves

Merging

Based on the idea of merging, think about an array a that has 2 halfs that have been sorted - how could we merge the two arrays?

Merging Algorithm

Before merging, we copy the input array a into aux. To merge we move keep track of three indexes: i and j are indexes in the first and second halfs of the aux array, we then iterate across the input array a. At each iteration we compare the values in aux[i] and aux[j] and set the smaller value to a[k], we then increment the intex of whichever half was smaller (i or j). Then we move to the next iteration of k

Furthermore, if we are at the end of i or j then we just use the other one

Merging Implementation

1
import { type Compare, Comparison } from './definition'
2

3
/**
4
 * Merges the data in the range `lo` to `hi` into `a`. Assumes that the two
5
 * halfs of `a` are already sorted as provided by the `lo`, `mid` and `hi`
6
 * indexes
7
 *
8
 * Copies the provided range into `aux` in order to track the original item
9
 * positions
10
 */
11
export const merge = <T>(
12
  compare: Compare<T>,
13
  array: Array<T>,
14
  aux: Array<T>,
15
  lo: number,
16
  mid: number,
17
  hi: number
18
) => {
19
  const lessThan = (a: T, b: T) => compare(a, b) === Comparison.Less
20

21
  // Copy items into the auxillary array
22
  for (let i = lo; i <= hi; i++) aux[i] = array[i]
23

24
  let l = lo
25
  let h = mid + 1
26

27
  for (let i = lo; i <= hi; i++) {
28
    if (l > mid) array[i] = aux[h++]
29
    else if (h > hi) array[i] = aux[l++]
30
    else if (lessThan(aux[h], aux[l])) array[i] = aux[h++]
31
    else array[i] = aux[l++]
32
  }
33
}

Sorting

Sorting Algorithm

The sorting algorithm splits the array recursively and and runs merge on it. This works since the smallest version of this array will always consist of 2 items which can always be considered to be 2 sorted halves

Sorting Implementation

1
import type { Compare } from './definition'
2
import { merge } from './mergesort-merge'
3

4
export const mergeSort = <T>(compare: Compare<T>, array: Array<T>) => {
5
  const aux = new Array<T>(array.length)
6

7
  const sort = (lo: number, hi: number) => {
8
    if (hi - lo < 1) {
9
      return
10
    }
11

12
    const mid = lo + Math.floor((hi - lo) / 2)
13

14
    sort(lo, mid)
15
    sort(mid + 1, hi)
16
    merge(compare, array, aux, lo, mid, hi)
17
  }
18

19
  sort(0, array.length - 1)
20
}

It is important to note that the aux array is allocated once and not within merge or sort. This is to prevent many additional arrays being created due to the fact that the algorithm is recursive

Comparison with Insertion Sort

Mergesort with Insertion

Since mergesort is recursive there can be a large function call overhead. For smaller values we can avoid this by using insertion sort (or another elementary sort) when the size of the subarray is smaller than a specific amount as part of our recursive exit condition:

1
import { type Compare, Comparison } from './definition'
2
import { merge } from './mergesort-merge'
3

4
const CUTOFF = 8
5

6
export const insertionSortRange = <T>(
7
  compare: Compare<T>,
8
  array: Array<T>,
9
  s: number,
10
  e: number
11
) => {
12
  const swap = (indexI: number, indexJ: number) => {
13
    const replaced = array[indexI]
14

15
    array[indexI] = array[indexJ]
16
    array[indexJ] = replaced
17
  }
18

19
  for (let i = s; i <= e; i++) {
20
    for (let j = i; j > 0; j--) {
21
      if (compare(array[j], array[j - 1]) === Comparison.Less) swap(j, j - 1)
22
      else break
23
    }
24
  }
25
}
26

27
export const mergeSortWithInsertion = <T>(
28
  compare: Compare<T>,
29
  a: Array<T>
30
): Array<T> => {
31
  const aux = new Array<T>(a.length)
32

33
  const sort = (lo: number, hi: number) => {
34
    if (hi <= lo + CUTOFF - 1) {
35
      insertionSortRange(compare, a, lo, hi)
36
      return
37
    }
38

39
    const mid = lo + Math.floor((hi - lo) / 2)
40
    sort(lo, mid)
41
    sort(mid + 1, hi)
42
    merge(compare, a, aux, lo, mid, hi)
43
  }
44

45
  sort(0, a.length - 1)
46

47
  return a
48
}

Analysis of Mergesort

• Uses at most N lg N comparisons and 6N lg N accesses
• Uses 2N space

Bottom Up Mergesort

Algorithm

If we think about the array as small subarrays of size 1, and merge those in pairs to get subarrays of size 2, then 4, and so on. Since we are working with small subarrays we can use our existing merge implementation as previously

Implementation

We can implement mergesort like this which allows us to avoid recursion

1
import type { Compare } from './definition'
2
import { merge } from './mergesort-merge'
3

4
export const mergeSortBottomUp = <T>(
5
  compare: Compare<T>,
6
  array: Array<T>
7
): Array<T> => {
8
  const length = array.length
9
  const aux = new Array<T>(length)
10

11
  for (let size = 1; size < length; size += size) {
12
    for (let low = 0; low < length - size; low += 2 * size) {
13
      const mid = low + size - 1
14
      const high = Math.min(low + 2 * size - 1, length - 1)
15

16
      merge(compare, array, aux, low, mid, high)
17
    }
18
  }
19

20
  return array
21
}

Sorting Complexity

Computational complexity is a framework for studying the efficiency of algorithms for solving a particular problem

We need the following for defining computational complexity

• Model of computation - what operations are allowed
• Cost model - how many times we do an operation
• Upper bound - guarantee provided by some algorithm for solving a problem
• Lower bound - limit for all different algorithms for solving a problem
• Optimal algorithm - the best possible algorithm for solving a given problem - the upper bound for this algorithm is approximately the same as the lower bound for a problem

The Sorting Problem

The idea of a lower bound identifies the minimum number of compares needed to ensure that a the sorting problem is solved - this can be determined using a decision tree

The result of this is that any sorting algorithm that is based on compares must use at least Nlg(N) compares in the worst case - the height of the decision tree formed - this is the lower bound for sorging

Since this is the complexity of merge sort, we can see that mergesort is optimal in terms of the number of compares, but since it uses extra space it is not space optimal

Note that this lower bound applies to the specific model of compares we are using for our example - in this case a comparison-based algorithm

Cases where there may be a more optimal case:

• Partially ordered arrays (Insertion sort)
• Lots of duplicate keys (3-way Quick Sort)
• Certain digit/character comparisons (Radix Sort)

Comparators

Comparators are a mechanism for sorting based on some specific value, in our case we have been using the compare function that we provide

The compare method provided must be a total order, for example if we are comparing strings we can consider many different things:

• Alphabetical
• Case insensitive
• Longest to shortest

In the above implementations as long as we provide a compare function that works for our data

Stability

I a typical use we often want to sort by one key and then by another, in this case we want to ensure that we don’t unsort a previous sort when running a new sort, so e.g. if we order by name and then age we still might want our data to be be stil relatively sorted

Stability is when an algorithm preserves the relative order of elements

• Insertion Sort - stable - we never move equal items past each other
• Selection Sort - unstable - we might have items move past other equal items when switching items
• Shell Sort - unstable - moves keys past other keys that may be equal
• Merge Sort - stable as long as the merge operation is stable. If the merge takes from the left subarray if two items are equal then the merge operation is equal since this ordering is retained