Out of Range

Chris invented a sort function, Best Sort that has a time complexity of $O(1)$ ! Although this is very efficient, it can only work on a range of less than 200 numbers. If Chris were to sort 300 numbers, he has several options as below :

1. Sort range $[0,100)$ , followed by $[1,101), [2,102)$ and so on. Perform this 2 times.

2. Sort range $[0,100)$ , followed by $[1,101), [2,102)$ and so on. Perform this 3 times.

3. Sort the first 200 numbers, then sort the last 200 numbers.

4. Sort the first 200 numbers, then sort the last 200 numbers, then sort the first 200 numbers again.

5. Sort the first 200 numbers, then sort the last 200 numbers, then sort the first 200 numbers again, and finally the last 200 numbers again.

Which options actually sort the numbers? And among them which is uses the least number of Best Sort ?

Details and Assumptions

• $[l,r) = \{ l,l+1,l+2,\dots, r-2,r-1 \}$
• The option $1,2,3-1$ implies option 1 , 2 and 3 works and 1 uses the least number of Best Sort .