Sorting Algorithm Proof

Question

Hydrosort is a sorting algorithm. Below is the pseudocode.

*/A is arrary to sort, i = start index, j = end index */

    Hydrosort(A, i, j):                 // Let T(n) be the time to find where n = j-1+1

      n = j – i + 1                              O(1)
      if (n < 10) {                              O(1)
        sort A[i…j] by insertion-sort            O(n^2) //insertion sort = O(n^2) worst-case
        return                                   O(1)
      }
      m1 = i + 3 * n / 4                         O(1)
      m2 = i + n / 4                             O(1)
      Hydrosort(A, i, m1)                        T(n/2)
      Hydrosort(A, m2, j)                        T(n/2)
      Hydrosort(A, i, m1)                        T(n/2)

How would I prove that Hydrosort(A, 1, n) correctly sorts an array A of n elements?

Answer 1

By induction on the number of elements. Assuming you believe insertion sort works, if $n \lt 10$ Hydrosort works because it just calls insertion sort. That is the base case. Now if $n \ge 10$ you partition the problem into three pieces. If none of them is $10$ or larger Hydrosort will work because each piece will work. How large can $n$ be so that no piece is $10$ or larger? Now you know Hydrosort works up to that $n$. Now if the partition results in all pieces of that $n$ or less you know Hydrosort works. You have to justify that if I start with a large $N$ of things to sort, the pieces will eventually get down to less than $10$. You can do this by showing that at each step the maximum allowable $n$ is multiplied by some number greater than $1$. Can you do that?

Answer 2

One helpful fact could be useful for both numerical (for small $n$) and theoretical proofs that sorting algorithm works correctly: if it is able to sort all $2^n$ binary combinations of $n$ bits, then it also will sort any sequence of $n$ numbers.