Cacher is the code snippet organizer for pro developers

Merge Sort

Compare the lowest element of each array in turn. 

Each time we compare the lowest element of each array, the lower one goes to the sorted array.

For example, we have left and right arrays that are sorted within them, now we try to merge these 2 arrays:

1	2	5	|	3	4	6

First compare the lowest for each array: 1 or 3. 1 is lower, so 1 goes to the beginning of the final sorted array.

After that, the next element in the left, becomes the lowest element in the left array. And the lowest element of the right array is still the same.

So now we compare the 2nd element of the left array with the first element of the right array: 2 or 3. 2 is lower, so it will become the 2nd element in the sorted array.

So now the 3rd element in the left array becomes the lowest element for the left side. And the lowest for the right side is still the first element on the right. So now we compare 5 and 3. This time the right side is lower. So 3 goes into the sorted array. And now the 2nd element of the right array becomes the lowest for the right side.

So we continue like this, until the 2 arrays are merged and sorted.

This algorithm is actually much more efficant than all other ways of sorting. The best and worst case time are both (n log n).

Recursion is used for merge sort. That's the reason that it's more effective.