#\$\Theta(N\cdot\sqrt N)\$ sort code-golf restricted-complexity array-manipulation The challenge is to write a program that sorts an array of distinct positive integers in ascending order. You may input the array and output the result using the default IO methods.

However, the worst-case time complexity of the algorithm used must be \$\Theta(N \cdot \sqrt N)\$, where \$N\$ is the length of the input array.

You may not assume your built-in sorting functions to have any time complexity in particular. While you can implement a fast (e.g. \$O(N \log N)\$) sort and then perform pointless operations to increase the complexity, direct algorithms exist.

This question is tagged code-golf, so the shortest code wins!

##Sandbox stuff I have noticed that a possible solution is, for example, to create a sorted multiset from the array and read it back. I would probably like to disallow that. Is there a way to achieve that without making the validity criteria subjective?

\$\Theta(N\cdot\sqrt N)\$ sort code-golf restricted-complexity array-manipulation

The challenge is to write a program that sorts an array of distinct positive integers in ascending order. You may input the array and output the result using the default IO methods.

However, the worst-case time complexity of the algorithm used must be \$\Theta(N \cdot \sqrt N)\$, where \$N\$ is the length of the input array.

You may not assume your built-in sorting functions to have any time complexity in particular. While you can implement a fast (e.g. \$O(N \log N)\$) sort and then perform pointless operations to increase the complexity, direct algorithms exist.

This question is tagged code-golf, so the shortest code wins!

Sandbox stuff

I have noticed that a possible solution is, for example, to create a sorted multiset from the array and read it back. I would probably like to disallow that. Is there a way to achieve that without making the validity criteria subjective?

#\$\Theta(N\cdot\sqrt N)\$ sort code-golf restricted-complexity array-manipulation The challenge is to implement an algorithm that sorts an array of distinct positive integers in ascending order. You may input the array and output the result using the default IO methods.

However, the worst-case time complexity of the algorithm used must be exactly \$\Theta(N \cdot \sqrt N)\$, where \$N\$ is the length of the input array.

Remember that I hacked into everybody's computers and replaced the built-in sorting algorithm with Slowsort - it takes non-polynomial time now! That is, you may not assume your built-in sorting functions to have any time complexity in particular. ^{C++'s std::sort_heap now implements the heap via a sorted array}

This question is tagged code-golf, so the shortest code wins!

#\$\Theta(N\cdot\sqrt N)\$ sort code-golf restricted-complexity array-manipulation The challenge is to write a program that sorts an array of distinct positive integers in ascending order. You may input the array and output the result using the default IO methods.

However, the worst-case time complexity of the algorithm used must be \$\Theta(N \cdot \sqrt N)\$, where \$N\$ is the length of the input array.

You may not assume your built-in sorting functions to have any time complexity in particular. While you can implement a fast (e.g. \$O(N \log N)\$) sort and then perform pointless operations to increase the complexity, direct algorithms exist.

This question is tagged code-golf, so the shortest code wins!

##Sandbox stuff I have noticed that a possible solution is, for example, to create a sorted multiset from the array and read it back. I would probably like to disallow that. Is there a way to achieve that without making the validity criteria subjective?