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})$