1. The problem statement, all variables and given/known data Consider the following sorting algorithm for an array of numbers (Assume the size n of the array is divisible by 3): • Sort the initial 2/3 of the array. • Sort the final 2/3 and then again the initial 2/3. Reason that this algorithm properly sorts the array. What is its running time? 2. Relevant equations 3. The attempt at a solution I was just thinking if I can prove this by using element-wise proof. The array is divided into 3 sub arrays, call it A,B and C. As long as I am applying the algorithm on the array, I pick an element in each sub-array and show why it's not sorted by explaining why this element can be in an another sub-array. At the end I show why it's sorted. Proof Sort the initial 2/3 of the array In B, we have the largest elements of the first 2/3 of the array sorted. The array is not sorted because some element in B may be greater than some element in C and some element in C may be less than some element in A. Sort the final 2/3 of the array Now the elements in C are sorted relatively to the array hence its elements which are the remaining elements of the array were sorted with the largest values of the first 2/3 of the array. A and B are not sorted relatively to the array because there could an element in C placed now in B less than some element in A. Sort initial 2/3 of the array Now A and B are sorted relatively to the array because A was sorted with the elements in C that could be less than the elements in A. So A, B and C are sorted relatively to the array which implies the array is sorted.