Mergesort algorithm implementation

Question

I have gone through Merge sort algorithm. I understood the logic, but I didn't get why we have to copy the b[] array again into the a[] array. What we have entered in the b[] array are sorted numbers only, right? But, if we print the b[] array, we are getting unsorted array. Once we copy it into the a[] array, we are getting the correct output. Can anyone explain why we have to copy the b[] array to the a[] array?

Algorithm::

void MergeSort(int low, int high) {
    if (low < high) { 
        int mid = (low + high) / 2;
        MergeSort(low, mid);
        MergeSort(mid + 1, high);
        Merge(low, mid, high);
    }
}

void Merge(int low, int mid, int high) {
    int h = low, i = low, j = mid + 1, k;
    while ((h <= mid) && (j <= high)) {
        if (a[h] <= a[j]) { 
            b[i] = a[h]; 
            h++;
        } else { 
            b[i] = a[j]; 
            j++;
        }
        i++;
    }
    if (h > mid) 
        for (k = j; k <= high; k++) {
            b[i] = a[k]; i++;
        }
    else 
        for (k = h; k <= mid; k++) {
            b[i] = a[k]; i++;
        }
    for (k = low; k <= high; k++) 
        a[k] = b[k];
}

Program I implemented:

import java.util.Arrays;

public class Msort {
    public static void msort(int[] arr, int l, int h) {
        int m;
        if (l < h) {
            m = (l + h) / 2;
            msort(arr, l, m);
            msort(arr, m + 1, h);
            merge(arr, l, m, h);
        }
    }

    public static void merge(int arr[], int l, int m, int h) {
        int i = l, j = m + 1, k = l, n;
        int[] sarr = new int[arr.length];
        while ((i <= m) && (j <= h)) {
            if (arr[i] <= arr[j]) {
                sarr[k] = arr[i];
                i++;
            } else {
                sarr[k] = arr[j];
                j++;
            }
            k++;
        }
        if (i <= m) {
            for (n = i; n <= m; n++) {
                sarr[k] = arr[n];
                k++;
            }
        } else {
            for (n = j; n <= h; n++) {
                sarr[k] = arr[n];
                k++;
            }
        }

        for (k = l; k <= h; k++) {
            arr[k] = sarr[k];
        }
        System.out.println("arr" + Arrays.toString(arr));
    }

    public static void main(String[] args) {
        int[] arr = { 12, 11, 13, 5, 6, 7 };

        Msort.msort(arr, 0, arr.length - 1);
    }
}

Please would you add the code where you call the merge sort function, so that we can see the context in which the a and b arrays are used. It would help to know what they contain before the call and are expected to contain after it. — Evil Dog Pie
– Evil Dog Pie, Commented Mar 26, 2015 at 9:49
possible duplicate of Understanding merge sort optimization: avoiding copies. There is a very nice explanation in this answer, much better than mine! — Evil Dog Pie
– Evil Dog Pie, Commented Mar 26, 2015 at 14:03

Evil Dog Pie · Accepted Answer · 2015-03-26 10:43:26Z

Merge sort works by splitting the unsorted data down into individual elements, a single element being considered sorted, and merging them back together in progrssively larger sorted chunks.

The b array is the 'work bench' in your implementation and, at the end of each iteration (recursion in your example), holds the result of the work done that iteration. The split is peformed by copying the left and right sides of the unsorted array into the b array.

In order to build the merged result as you come 'back up' from splitting the array, you need to rebuild the result from the components, which is done by copying the sorted chunk back over it's unsorted original.

The copy can be avoided if the recursion is changed so that the direction of the merge (left to right or right to left / low to high or high to low) corresponds with the level of the recursion. Full copy-in-place merge sort, without the b array, is a more complicated alogrithm.

Collectives™ on Stack Overflow

Mergesort algorithm implementation

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related