Solution Sketch

Subtask 1

For the first subtask, we can use any sort that swaps adjacent elements, such as bubble sort or insertion sort. These sorts take ~\mathcal{O}(N^2)~ comparisons and swaps.

Time Complexity: ~\mathcal{O}(N^2)~

Subtask 2

For the second subtask, we recall that insertion sort works best when the array is nearly sorted. We will consider a solution where for each ~k~ from the largest ~k~ where ~2^k \le N~, down to ~1~, we will use insertion sort to sort all elements that are distance ~2^k - 1~ apart from each other, relative to one another. This can be thought of as arranging the array into approximately ~2^k - 1~ rows each with approximately ~\frac{N}{2^k - 1}~ elements, and sorting each row.

Well versed programmers will recognize this as shell sort with Hibbard's gap sequence. It can be shown that this takes ~\mathcal{O}(N \cdot \sqrt{N})~ comparisons and swaps in the worst case. Extra care should be taken to ensure that a correct insertion sort break condition is used.

Time Complexity: ~\mathcal{O}(N \cdot \sqrt{N})~