1. Prove that the following algorithm sorts its input data; i.e., that data[1] ≤ data[2] ≤ ... ≤ data[n] when the algorithm terminates. You may assume that data contains at least one element. Also, bxc represents the floor function, which returns the largest integer less than or equal to the given value (e.g., b3.1415c = 3). Input: data: an array of integers Input: n: the length of data Output: a reordering of data in (ascending) sorted order 1 Algorithm: ThirdSort 2 if n = 1 then 3 return data 4 else if n = 2 then 5 if data[1] data[2] then 6 Swap data[1] and data[2] 7 end 8 return data 9 else 10 third = bn/3c 11 Call ThirdSort on data[1..n-third] 12 Call ThirdSort on data[third+1..n] 13 Call ThirdSort on data[1..n-third] 14 return data 15 end Hint: use strong induction on the length of data. You may find it useful to assign names (like A, B, and C) to the three “thirds” of the data array given by data[1..third], data[third+1..n-third], and data[n-third+1..n]. You may also find it helpful to simulate the algorithm on some small inputs to understand what it is doing.
