mergesort algorithm

MERGE-SORT(A, low, high)
If low < high
    mid = (low + high) / 2
    MERGE-SORT(A, low, mid)       // Sort first half
    MERGE-SORT(A, mid + 1, high)  // Sort second half
    MERGE(A, low, mid, high)      // Merge the sorted halves










MERGE(low, mid, high)
{
    h = low        // Pointer for the first subarray (a[low : mid])
    i = low        // Pointer for the auxiliary array (b[])
    j = mid + 1    // Pointer for the second subarray (a[mid + 1 : high])

    // Merge the two sorted subarrays into b[]
    while (h <= mid) and (j <= high) do
    {
        if (a[h] <= a[j]) then
        {
            b[i] = a[h]
            h = h + 1
        }
        else
        {
            b[i] = a[j]
            j = j + 1
        }
        i = i + 1
    }

    // Copy remaining elements from the first subarray, if any
    if (h > mid) then
        for k = j to high do
        {
            b[i] = a[k]
            i = i + 1
        }
    else
        for k = h to mid do
        {
            b[i] = a[k]
            i = i + 1
        }

    // Copy merged elements back to the original array
    for k = low to high do
        a[k] = b[k]
}