When sorting using merge sort, I get confused about what going on. Consider the following array A = [7,5,2,8,9,1] and the following code:

--------------------------------------------------------------------------------------------------------------------------

int merge_sort(int *input, int start, int end) { if (start < end) { int middle = (start + end ) / 2; merge_sort(input, start, middle); merge_sort(input, middle+1, end); merge(input, start, middle, end); }

return 0; } int merge(int *input, int left, int middle, int right) { // determine lenghts int length1 = middle - left + 1; int length2 = right - middle; // create helper arrays int subarray1[length1]; int subarray2[length2]; // fill helper arrays int i; for (i=0; i

int j,k; j = 0; i = 0;

// go through subarray and insert into main array for (k=left; k<=right; ++k) { if (subarray1[i] <= subarray2[j]) { input[k] = subarray1[i]; ++i; } else if (subarray1[i] > subarray2[j]) { input[k] = subarray2[j]; ++j; } }

return 0; } -------------------------------------------------------------------------------------

Since merge-sort () is called first on array A, the left side of this array would recursively divided using, merge-sort(input, start , middle) until base case (start

<7,5,2,8,9,1>

<7,5,2>

<7,5>

<7>

Then we can deal with the right using merge-sort(input, middle + 1, end)

<7,5>

<5>

<7,5,2>

<2>

<8,9,1>

<8,9>

...

until we get something like: < 7 > < 5 > < 2 > < 8 > < 9 > < 1 >

This where we should merge(at least I think) using merge (input, start, middle, end)

Which would sort 7 and 5 into < 5 , 7 >

Which would make the first iteration of Merge Sort = [5, 7 , 2 , 8 , 9 , 1]

Am I right, or am I missing something? I have used visualalgo to visualize how Merge sot works, and it is different from the visuals from "introduction to algorithms." I would assume that since we recursively call merge-sort using merge-sort(input, start, middle) the left side is "divided" first since programming works top to bottom, and when the base case is met start >=end that is when we can move to the next recursive call on the right side, aka merge-sort(input, middle + 1, end). Then we can finally "conquer" and "combine" by calling merge(input, start, middle, end), which will create subarrays (1 and 2) of different sizes ( based on what is the size of what we want to sort, aka left, middle and right). Sorry for the rambling, by I hope by giving my approach on how I see this, someone can better assist me with figuring out how the first iteration or pass of Merge sort looks like.