> For the complete documentation index, see [llms.txt](https://cs-notes.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs-notes.gitbook.io/algorithm-notes/outline/overview-2/merge-sort.md).

# Merge Sort

As a typical [DnC](broken://pages/-LQpLueuStjmV1CIsFw6) algorithm, MergeSort tries to solve sorting problem in a recursive, distributed way. Its overall algorithm outperforms the [InsertionSort](/algorithm-notes/outline/overview-2/insertion-sort.md) and canonical [BubbleSort](/algorithm-notes/outline/overview-2/bubble-sort.md) algorithms.

## Fundamental Ideas

MergeSort algorithm takes the unsorted original array and split it into С number of sub-arrays, feeding them individually into the algorithm itself for the same sorting purpose.

Then, resolve each sub-problem with the defined minimal length of sub-array. After recursive calls in each layer of division, combining the results of each subroutine to generate the final sorting solution.

***Note**: the task's aim might varies with scenarios. e.g. a bulk of sorted arrays reside in memory has to merge into an array with randomly filled elements; therefore, the actual implementation is not definite.*

## Pseudocode

Though the abstract details are the same, the [top-down MergeSort](/algorithm-notes/outline/overview-2/merge-sort.md#top-down-approach) and [bottom-up MergeSort](/algorithm-notes/outline/overview-2/merge-sort.md#bottom-up-approach) are two different implementations of [MergeSort](/algorithm-notes/outline/overview-2/merge-sort.md#merge-sort). The first one is suitable for education for its simplicity while the second one has a slightly better performance and widely adopted in many libraries.

### Top-down Approach

It is a common practice to use such a recursive approach:

```
TOP_DOWN_MERGE_SORT(array, low, high, new_array)
  if high - low < 2
    return

  middle := (low + high) / 2
  TOP_DOWN_MERGE_SORT(array, low, middle, new_array)
  TOP_DOWN_MERGE_SORT(array, middle, high, new_array)

  TOP_DOWN_MERGE(array, low, middle, high, new_array)

  MERGE(array, low, middle, high, new_array)
```

### Bottom-up Approach

rather than a recursive method in above approach, using a iterative method:

```
BOTTOM_UP_MERGE_SORT(array, new_array)
  for width := 1, width < length(array)
    for i := 0, i < length(array)
      MERGE(array, i, min(i+width, n), min(i+2*width, n), new_array)
      i := i + 2 * width
    width := width * 2
```

and the universal MERGE step:

```
MERGE(array, low, middle, high, new_array)
  i := low
  j := middle
  for k in range (high - low)
    if i < middle and array[i] < array[j]
      new_array[k] = array[i]
      i := i + 1
    else if j < high and array[j] < array[i]
      new_array[k] = array[j]
      j := j + 1
```

## Algorithm Analysis

[MergeSort](/algorithm-notes/outline/overview-2/merge-sort.md#merge-sort) is a [stable](broken://pages/-LQpLuf2ZYeNKgv4W400) sorting scheme that has [average and worst-case](/algorithm-notes/outline/asymptotic-analysis.md) running times of Ο(n ⋅ log(n)) regardless of the inputs.

It is simple to prove the running complexity by [master method](/algorithm-notes/outline/overview/master-method.md) Τ(n) = 2 Τ(n/2) + Θ(n)

## Additional References

1. Combining [MergeSort](/algorithm-notes/outline/overview-2/merge-sort.md#merge-sort) and [InsertionSort](/algorithm-notes/outline/overview-2/insertion-sort.md): <https://cs.stackexchange.com/questions/68179/combining-merge-sort-and-insertion-sort>