Hi I need help to prove the correctness of a recursive algorithm.
It works like this, it takes an input array A with the size of the array being a power of 4.
The algorithm is defined like this:
sort(array):
Base case:
if n <= 4, then directly sort the input array using insertionsort and return the sorted array.
Recursive call 1: recursively sort the first 3/4ths of the array
Recursive call 2: recursively sort the upper 2/3 of the previously sorted 3/4ths with the unsorted 1/4th
Recursive call 3: recursively sort the lower 1/3 of the first recursive call with the sorted lower 2/3 of the 2nd recursive call
return the sorted output of recursive call 3 and append the upper 1/3 of the 2nd recursive call
I'm supposed to do this with induction.
My attempt:
I can reason that the order of the sorts will give a correct output since after the first recursive sort, the lowest values of the first 3/4ths are stored in the lowest 1/4th, then after the 2nd recursive sort, the biggest values will be stored in the upper 1/4th of its output, then in the third recursive sort we correctly sort the lower values, and finally return the correctly sorted lower values with the correctly sorted higher ones appended to its end.
I think what I need to do is to prove with induction that the individual recursive sorts are correct, and then reason like I did above to prove that the whole algorithm is correct.
I am struggling to prove that the recursive sorts sort correctly.
My attempt at induction:
The array is obviously sorted for inputs <= 4, so when the input is 4^1 (base case), the algorithm correctly sorts the input array.
Now I assume that it works for 4^p, and try to prove that it works for when t = p+1 $$n = 4^t, p >= 1$$
It is bigger than 4, so it gets called on recursively, with its size reduced
$$3/4 * 4^t = 3 * 4^p$$
And now I don't know what to do.
Any help would be appreciated, thanks.
