Autism Challenge

You have array A[1..N].
Subarrays A[1..M] and A[M+1..N] (1 < M < N) are sorted in ascending order.

Task is to sort inplace A[1..N] in O(N) time and O(1) additional memory

>>1

... If you use 1-based indexing then you must have 1<=i ... =)

... You lose the fact that... memory location can be added in n-elemtns array... subsequence of natural numbers...

...Also quicksort but .. not bubble... =)