CODEWITHSUNDEEP
javaalgorithmsortingdata-structuresmergesort
sharad_kalya
sharad_kalya

Reputation: 275

How this particular merge sort program is working?

I am learning sorting algorithms. I have gone through a program given on the following link. For the sake of simplicity I am attaching both link and program itself.

public class Mergesort {
private int[] numbers;
private int[] helper;
private int number;

public void sort(int[] values) {
    this.numbers = values;
    number = values.length;
    this.helper = new int[number];
    mergesort(0, number - 1);
}

private void mergesort(int low, int high) {
    if (low < high) {
    int middle = low + (high - low) / 2;
    mergesort(low, middle);
    mergesort(middle + 1, high);
    merge(low, middle, high);
    }
}

private void merge(int low, int middle, int high) {
    for (int i = low; i <= high; i++) {
        helper[i] = numbers[i];
    }
    int i = low;
    int j = middle + 1;
    int k = low;
    while (i <= middle && j <= high) {
        if (helper[i] <= helper[j]) {
            numbers[k] = helper[i];
            i++;
        } else {
            numbers[k] = helper[j];
            j++;
        }
        k++;
    }
    while (i <= middle) {
        numbers[k] = helper[i];
        k++;
        i++;
    }
}

}

I am not getting any clue that in merge method why this last while(i<=middle) is included. Means while(j<=high) was also there, but this condition was ignored. The link where I got this program is http://www.vogella.com/tutorials/JavaAlgorithmsMergesort/article.html

Sorry for my bad explanation. Hope someone can explain it to me.

Upvotes: 0

Views: 54

Answers (1)

lexicore
lexicore

Reputation: 43671

The clue is actually in the referenced article:

            // Copy the rest of the left side of the array into the target array
            while (i <= middle) {
                    numbers[k] = helper[i];
                    k++;
                    i++;
            }

Consider the case when numbers in the first half are all greater than the numbers in the second half. Then in the first while cycle you'll only increase j, you will not copy any numbers from the first half. The second while cycle copies the remaining numbers from the first half.

A good question is why you actually don't need to copy tthe remaining numbers from the second half. I'll leave it to you. :)

Upvotes: 2

Related Questions