-2

In the merge_sort part, there are multiple calls to the same function within the recursive. How are the other two executed when the definition holds that till a condition is false, the recursion does not stop?

T tempArray[right - left + 1];

        int pos = 0;
        int left_pos;
        int right_pos = mid + 1;

        while (left_pos <= mid && right_pos <= right) {

            if (array[left_pos] < array[right_pos]) {
                tempArray[pos++] = array[left_pos++];

            } else {
                tempArray[pos++] = array[right_pos++];
            }
        }

        while (left_pos <= mid) {
            tempArray[pos++] = array[left_pos++];
        }

        while(right_pos <= right) {
            tempArray[pos++] = array[right_pos++];

        }

        for(int iter = 0; iter < pos; iter++) {
            array[iter + left] = tempArray[iter];
        }

        return;
}

static void merge_sort(T* array, int left, int right) {

        int mid = (right + left) / 2;

        // We have to sort only when left < right because when left==right it is anyhow sorted

        if (left < right) {
            // Sort the left part//

            merge_sort(array, left, mid);

            merge_sort(array, mid + 1, right);

            _merge(array, left, mid, right);
        }

        return;
    }
}

closed as off-topic by gnat, user22815, psr, TZHX, Michael Kohne Jul 8 '16 at 16:36

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions asking for assistance in writing or debugging existing code are off-topic on Programmers. These questions can be asked on Stack Overflow if they include the desired behavior, a specific problem or error, and the shortest code necessary to reproduce it in the question itself. See How To Create a Minimal, Complete, and Verifiable Example." – gnat, Community, psr, TZHX, Michael Kohne
If this question can be reworded to fit the rules in the help center, please edit the question.

6

A properly-designed recursive function always has three elements:

  1. The work that occurs in the current function call,
  2. The recursive function call, and
  3. The exit strategy.

The exit strategy in your question's code occurs in the first function when all of the while conditions are finally satisfied and the function executes the return statement.

Have a look at this excellent animation from Penjee's blog, which illustrates how a Fibonnaci recursive function works:

enter image description here

Notice that the return values combine to produce the final value for the function, and how the exit strategy bubbles from the bottom of the call tree to the top. This essentially works the same way in the TempArray function in your question.

Not the answer you're looking for? Browse other questions tagged or ask your own question.