-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;
    }
}
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.