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

It's unforgivable to use 1-based indexing unless your an elementary school child.

http://en.wikipedia.org/wiki/Merge_sort

Cool homework bro.

>>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... =)

>>4
Fuck off, Mugenjohncel.

>>5
You're supposed to tell him to go back to /smuggling onions/

>>6
You were supposed to tell me to go back to /jp/.

>>4
... =)
Stop that

http://www.autismawareness.com/articles/090311-touhou-linked-to-autism.html

>>8
... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =) ... =)

>>1

It's pretty easy to do that with O(1) memory with lists, but I don't think it is possible with arrays.

>>11
O(1) = 1 Turing machine of memory.

>>10
This is like touhou but with more cancer.