Merge Sort

Merge Sort is an efficient method for sorting elements in an array, based on the following idea: if the first half of the array is sorted and the second half is also sorted, by merging these two halves, the entire array will be sorted.

Merge Sort is a typical example of a divide and conquer algorithm: it sorts a sequence delimited by indices st and dr:

• if st <= dr, the problem is elementary, as the sequence is already sorted
• if st < dr:
• the problem is divided into subproblems by identifying the middle of the sequence, m = (st + dr) / 2;
• the subproblems are solved by sorting the sequence delimited by st and m, and the sequence delimited by m+1 and dr – recursive calls;
• the solutions are combined by merging the two sequences; in this way, the sequence delimited by st and dr is sorted.

In the following sequence, the tmp array is considered globally declared, of the same size as v:

void MergeSort(int v[], int st, int dr)
    {
        if(st < dr)
        {
            int m = (st + dr) / 2;
            MergeSort(v, st , m);
            MergeSort(v, m + 1 , dr);
            // Merging
            int i = st, j = m + 1, k = 0;
            while( i <= m && j <= dr )
                if( v[i] < v[j])
                    tmp[++k] = v[i++];
                else
                    tmp[++k] = v[j++];
            while(i <= m)
                tmp[++k] = v[i++];
            while(j <= dr)
                tmp[++k] = v[j++];
            for(i = st , j = 1 ; i <= dr ; i++ , j++)
                v[i] = tmp[j];
        }
    }

Observations:

• the complexity of merge sort is O(n ⋅ log n)
• merge sort requires additional memory space, the size of the array being sorted;
• in the above sequence, the tmp array is declared globally; declaring it locally can lead to stack overflow; a solution for this situation could be dynamic allocation of the auxiliary array.