It can be proven that sorting by comparison will take in the worst case scenario around N*log(N) comparisons. The actual lower limit is log2(N!) - like in sorting by insertion. However, this is close to N*log(N) for big N. One thing that you can optimize is the cache access, that can really make a huge time difference (like 10*X) at the same number of operations. Another thing is to optimize common cases. Often you need to sort arrays that contain many parts that are already monotonic. The sort used in PHP will be very efficient for such cases. A curiosity: you can sort 32bits integers in O(N) operations, adding each number to a binary tree with 32 levels, based on its bits: 0=left, 1=right. In the leafs, you just count the occurrences. Then walk the tree from left to right. This seems to contradict the above. The catch is that there are 2^32 distinct integers and log2(N) = log2(2^32) = 32. So, for integers, log(N) is really a small constant that can be ignored. You can sort more than 2^32 integers with the same complexity, because there will be duplicates but the tree will have at most 2^32 leafs. However, the memory access pattern and additional memory might make this algorithm less appealing in practice. And a half joke: sorting is computationally harder than chess: https://meaningofstuff.blogspo...

For me Java NIO (SocketChannel/select/read) worked a lot better then the multi-threaded/blocking version (Socket/read). I had to simulate 5000 TCP clients reading at 128kbps (radio streams), on Linux 2.6 64bits with 4GB RAM, CPU DualCore (Java 1.6). With the multi-threaded version is was a bit easier to code, but it consumed 2*100% CPU before reaching the target. The context switches between threads consumed a lot of CPU. Even before reaching the CPU limit, the Thread.sleep() between reads started to have big delays (>1second), probably because of the scheduler that had to schedule 5000 active threads. With the single-threader, NIO version it reached the target consuming about 20% of one CPU. I had to tweak a bit the reads for this. The problem was that reading in a close loop, there were many short reads, producing many switches between user/kernel space, consuming too much CPU. Putting a small sleep (50-100ms) between each select() resulted in bigger and fewer reads, in the same time consuming all the received data in a single loop.