Merge two sorted arrays with recursion without 3nd array-CodePudding

I'm a computer science student in my first year. I was given a task in recursion. I need to write a recursive function that gets two arrays and they are their physical size (non-negative) and sorts the arrays and puts them into the second array in a sorted way without an array set up for help. Presumably the size of the second array is sufficient. I can not write code that works for me, I would love for you to help me.

CodePudding user response：

So you have two sorted arrays, and we assume the second array has extra space allocated to hold the merged array.

Here's what that looks like in memory:

array0, length 4
 ------- 
|a|b|d|h|
 0-1-2-3 

array1, length 3
 ------------- 
|b|c|e| | | | |
 0-1-2-3-4-5-6

The extra space is at the end of array1's storage.

After we have finished merging the arrays, what value will be at index 6 of array1? Since index 6 will be the last element in the merged array, it will be the largest element of either input array. Since the input arrays are already sorted, it will be either the last element of array0 or the last element of array1. Let's compare them and copy the larger element to index 6. Since h is larger than e, we copy h to index 6. Since we have now put the last element of array0 in its final position, we can pretend that array0 is now length 3.

array0, length 3
 ------- 
|a|b|d| |
 0-1-2-3 

array1, length 3
 ------------- 
|b|c|e| | | |h|
 0-1-2-3-4-5-6

Now we do the same thing again for index 5 of array1. We compare the last elements of the (shortened) array0 and array1. Since e is larger than d, we copy e to index 5 and reduce the length of array1 by 1:

array0, length 3
 ------- 
|a|b|d| |
 0-1-2-3 

array1, length 2
 ------------- 
|b|c| | | |e|h|
 0-1-2-3-4-5-6

Repeat until input arrays have been shortened to length 0, and array1's storage will be filled with the final merged array.

CodePudding user response：

yes the arrays are sorted........