Merge Sort

Average time complexity - O(n * log(n))

Best-Case time complexity - O(n * log(n))

Worst-Case time complexity - O(n * log(n))

Worst-case space complexity - O(2)

Merge Sort is an algorithm that takes the same amount of time no matter how the array is arranged beforehand. It splits the array in two down the middle, then splits each of those in two, then all four of those in two, and so on until it has splits everything into one individual element.

Let's use the following array as an example:

4, 1, 5, 2, 3

Merge Sort will split it into two. The first half would look like this:

4, 1

Merge Sort then splits this into two. First half would look like this:

4

The second half would be:

1

Merge Sort then starts the merge process on this part. It compares 4 and 1, and places them in order.

1, 4

Now Merge Sort returns and starts working on the second half of the original list..

5, 2, 3

It then splits this in two. The first half would just be the number 5.

5

Nothing to do, so return and start on the second half.

2, 3

Now here it splits the array in two again. First half is:

2

Second half is:

3

It compares these two items, and merges them back in order.

2, 3

Now it compares the first half of the three-element array with the second half. For recollection, here's what those two halves look like:

5

2, 3

It compares 5 with 2. 2 is smaller, so it places it at the beginning.

2

Now it has the following arrays:

5

3

Now it compares 3 with 5. 3 is smaller, so it places it right after 2.

2, 3

Finally, it places 5 at the end, as it is left over.

2, 3, 5

Now it has the following to arrays:

1, 4

2, 3, 5

It begins the merge process on these.

It compares 1 with 2. 1 is smaller, so it places it at the beginning.

1

Now it has the following leftover arrays:

4

2, 3, 5

Next it compares 4 with 2. 2 is smaller, so it adds that to the sorted array.

1, 2

Now it has the following left over:

4

3, 5

Now it compares 4 with 3. 3 is smaller, so it places it into the sorted array.

1, 2, 3

Now it has the following leftovers:

4

5

It finally compares 4 with 5. 4 is smaller, so it adds that to the sorted array.

1, 2, 3, 4

Now it just has the 5 left over, so it adds that. The result is the sorted array.

1, 2, 3, 4, 5