Merge sort algorithm

Merging

Comparisons done:

Moves done:

Legend:
12	- elements belonging to the first part of the array
12	- elements belonging to the second part of the array
29	- elements being compared
10	- elements being merged into the new array
12	- yet unchecked elements

Merge sort

Comparisons done:

Moves done:

Legend:
12	- elements belonging to the first part of the array
7	- elements of the currently being sorted sub-array
24	- elements belonging to the second part of the array

The merge sort algorithm is a divide-and-conquer algorithm. The main idea of the method is to cut the original array into two halfs, sort each half separately, and then merge them. Since we can use the same merge sort method to sort both pieces of the original array, this is a recursive algorithm. That is, function merge_sort() calls itself (twice) with different argument. Thus, the implementation of the method is really simple. The first approximation can look like

void merge_sort(int data[], int first, int last)
{
   int middle = (first+last) / 2;
   merge_sort(data, first, middle);
   merge_sort(data, middle+1, last);
   merge(data, first, middle, last);
}

Of course, this is not the final version, because this implementation never stops. We need to test the size of the array to sort and sort only if we actually have to. How to merge two arrays (function merge()) is described in the first section of the page.