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

1 Answer 1

7

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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.