The original algorithm

Merge sort should be called “split-merge sort”, as it requires two a split phase, followed by a merge phase. Let us consider an example of integers.

-2, 3, 2, 4, 0, -1, 3, 4, -3, 1
We first organize the list into longest “runs”. A run is a sub list that is already sorted.
(-2, 3), (2, 4), (0), (-1, 3, 4), (-3, 1)
Next, we combine every other runs into two separate lists:
- -2, 3, 0, -3, 1
- 2, 4, -1, 3, 4
Then, we merge the two lists by picking the an item from each list to maximum the length of a run int he final list:
- pick -2 from in 1
  - in 1: 3, 0, -3, 1
  - in 2: 2, 4, -1, 3, 4
  - out -2
- pick 2 from in 2
  - in 1: 3, 0, -3, 1
  - in 2: 4, -1, 3, 4
  - out -2, 2
- pick 3 from in 1
  - in 1: 0, -3, 1
  - in 2: 4, -1, 3, 4
  - out -2, 2, 3
- pick 4 from in 2
  - in 1: 0, -3, 1
  - in 2: -1, 3, 4
  - out -2, 2, 3, 4
- pick -1 from in 2
  - in 1: 0, -3, 1
  - in 2: 3, 4
  - out -2, 2, 3, 4, -1
- pick 0 from in 1
  - in 1: -3, 1
  - in 2: 3, 4
  - out -2, 2, 3, 4, -1, 0
- pick 3 from in 2
  - in 1: -3, 1
  - in 2: 4
  - out -2, 2, 3, 4, -1, 0, 3
- pick 4 from in 2
  - in 1: -3, 1
  - in 2:
  - out -2, 2, 3, 4, -1, 0, 3, 4
- pick -3 from in 1
  - in 1: 1
  - in 2:
  - out -2, 2, 3, 4, -1, 0, 3, 4, -3
- pick 1 from in 1
  - in 1:
  - in 2:
  - out -2, 2, 3, 4, -1, 0, 3, 4, -3, 1
now, we turn around, and use the output list as the input list and repeat the whole process again