Merging in merge sort without using temporary arrays

Question

I'm trying to implement merge sort but somehow have been stuck for a day.

[Sorry for pasting a big amount of code but wouldn't be able to do without it]

Implementation:

Merge Sort - Function

int mergeSort(int arr[], int low, int high)
{
    int half = (low + high) / 2;    /* Find the middle element */ 
    if (low < high) {
        if (high - low == 1)        /* If only one element, return */
            return;
        mergeSort(arr, low, half);  /* Sort First Half */
        mergeSort(arr, half, high); /* Sort Second Half */
        merge(arr, low, half, high); /* Merge */
    }
    return SUCCESS;
}

Merging Step - Merge Function

int merge(int arr[], int low, int half, int high)
{
    int i = 0, j = 0, k = 0, l = 0, temp;    /* Initialize indices */

    for (i = low, j = half; i < half && j < high; i++, j++) { 
        /* Swap in the array itself if the elements are out of order */
        if (arr[i] > arr[j]) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    i = 0, j = low;  /* Compare and copy the elements in a global arrray C */
    for (k = 0; k < SIZE && i < low && j < high; k++) {
        if (arr[i] < arr[j]) {
            c[k] = arr[i];
            i++;
        } else {
            c[k] = arr[j];
            j++;
        }
    }
    
    if (i < j) { /* Copy remaining elements to the end of the array C */
        for (l = i; l < low; l++) {
            c[k++] = arr[l];
        }
    } else {
        for (l = j; l < high; l++) {
            c[k++] = arr[l];
        }
    }

Output

8 --> 9 --> 
4 --> 5 --> 8 --> 9 --> 
4 --> 5 --> 8 --> 9 --> 
1 --> 2 --> 4 --> 5 --> 8 --> 9 --> /* Sorting when left is sorted but right is in the process ? */
4 --> 5 --> 6 --> 7 --> 8 --> 9 --> 1 --> 2 --> 
1 --> 2 --> 4 --> 5 --> 6 --> 7 --> 8 --> 9 --> 
1 --> 2 --> 6 --> 7 --> 4 --> 5 --> 8 --> 9 --> 

     

Problem Description

I'm not using any local array for storing the elements of the array. Instead the elements are swapped if they are out of order and then copied into a global array by comparison Example: If I have the array

{ 9, 8, 4, 5, 2, 1, 7, 6 }

Then, firstly {8,9} would be sorted and then {4,5} would be sorted and then when copying procedure i.e {8,4} would be compared and so on. The following recursive calls take place

mergeSort(0,8) -> mergeSort(0,4) , mergeSort(4,8), merge(0,4,8)
mergeSort(0,4) -> mergeSort(0,2) , mergeSort(2,4), merge(0,2,4)
mergeSort(0,2) -> 1 element calls
and so on.

When merge is called when {4,5,8,9} are sorted , and the right is called merge(4,5,6) I have the following array

{4,5,8,9,1,2,7,6}

So, the algo tries to sort {4,5,8,9} and {1,2} when {1,2} is not a part of this subproblem i.e I want {1,2} and '{6,7} to become {1,2,6,7} and then combine both of these.

How do I overcome this? I have been stuck for so many hours.

Thanks a lot

Answer 1

In-place MergeSort is rarely, if ever used, because an in-place Merge operation, though possible, is quite complicated compared to the obvious version using an extra buffer.

Though rarely suggested, an efficient version can be obtained by alternating the merges between the original and extra buffers, to minimize the number of moves. Care must be taken that an even number of merges be made across the recursive calls. This can be handled by implementing true in-place merges for very small number of elements (or alternative sorts).

Answer 2

Your algorithm is flawed:

• the mergeSort function cannot be called with an empty slice: if (high - low == 1) should be changed to if (high - low < 2). As coded, an empty slice (low == high) will cause an infinite recursion triggering a stack overflow.
• the first loop in the merge function is incorrect: swapping the elements pairwise in the initial loop may cause the halves to become unsorted: merge({1, 4, 1, 2, 3}, 0, 2, 5) changes the halves to {1, 2} and {1, 4, 3}, which is no longer sorted.
• the merge loop into the global array c stops at SIZE elements (probably the length of c) so slices larger than SIZE are not handled.
• furthermore, you do not test this limit in the subsequent loops, potentially causing a buffer overflow for large slices.
• the test if (i < j) is incorrect: it should be if (i < half). As coded, the remaining elements in the second half are only copied if they are all greater than the first half.
• you never copy back from the global array to the original slice, hence the merge is ineffective.
• Your claim Merging in merge sort without using temporary arrays is unwarranted: the global array c is a temporary array.

Implementing merge sort in place without temporary arrays is difficult and less efficient than other sorting methods. There is no need for 2 temporary arrays, one with a length of half - low suffices, but allocating it with automatic storage is risky for large sorts and allocating from the heap is slow if performed at each step. Efficient and safe implementations allocate a single temporary array of length len / 2 at the start of the sort, passing it recursively along the steps and using it in the merge phases. At the cost of twice the space, merge sort can be implemented by alternating source and destination arrays when recursing.

Merge sort can be implemented simply with a single temporary array of limited size, increasing the complexity to O(n²) but only for very large arrays and a slow degradation of performance as n increases.