I loved whole L. Spiro's post, but I have something to correct
Sorting 2 smaller queues is faster than 1 big one.
This is a half truth.
Sorting can take:
- Best Case: O(N)
- Avg. Case: O( N log( N ) )
- Worst Case: O( N^2 )
1. In best case, N/2 + N/2 = N; so in theory it doesn't matter whether it's split or not. But there is the advantage that two containers can be sort in separate threads. So it's a win.
2. In the average case, 2 * (N/2 log(N/2)) > N log(N); having one large container should be faster than sorting two smaller ones (though there remains to be seen whether threading can negate the effect up to certain N)
3. In the worst case, 2 * (N/2)^2 < N^2; which means it's much better to sort two smaller containers than a large one.
In the end you'll have to profile as it is not a golden rule.
Spiro's suggestion of using temporal coherence assumes that most of the time you can get O(N) sorting using insertion sort; thus most likely having two smaller containers should be better (if you perform threading).
While I love your posts in general, this "correction" doesn't seem right to me. Specifically #2. With O( N log N ) run time -- worse than linear -- divide and conquer is beneficial when possible.
Plugging actual numbers into your inequality in 2 (N=1024, using base 2 log):
left side expansion: 2*(1024/2) log (1024/2) = 1024 * 9
right side expansion: 1024 log 1024 = 1024 * 10
The left side is LESS, contrary to your inequality.
Sorting 2 half-sized arrays is sometimes faster but never slower than a single full-size sort.
Perhaps you were thinking of searching with O( log N ) run time -- better than linear. In that case, doing divide and conquer IS harmful.