nuclearwinter27
nuclearwinter27

Reputation: 83

Merge sort function in C

I have the following piece of code which represents a merge sort function

/* perform merge sort */
void merge_sort(int arr[], int left, int right) {
    if (left < right) {
        int middle = left + (right - left) / 2;
        merge_sort(arr, left, middle);
        merge_sort(arr, middle + 1, right);
        merge(arr, left, middle, right);
    }
}

What is the use of this merge_sort(arr, middle + 1, right);?

Upvotes: 0

Views: 225

Answers (1)

Fred Larson
Fred Larson

Reputation: 62123

The basic idea of the merge sort algorithm is to divide the sequence to be sorted in half, sort each half, and then merge them together. This is frequently done recursively, as in this case. As a result, there must be two recursive calls, one for each half of the sequence.

If the merge_sort(arr, middle+1, right); call were not present, the algorithm would not be complete and the sort would not work.

As an experiment, you could try writing an example program using the merge sort function you posted. Try it with and without the line in question and see what results you get.

Upvotes: 1

Related Questions