On Sat, 17 Dec 2005 00:03:25 -0500, Tom Lane <tgl@sss.pgh.pa.us>
wrote:
>I've still got a problem with these checks; I think they are a net
>waste of cycles on average. [...]
> and when they fail, those cycles are entirely wasted;
>you have not advanced the state of the sort at all.
How can we make the initial check "adavance the state of the sort"?
One answer might be to exclude the sorted sequence at the start of the
array from the qsort, and merge the two sorted lists as the final
stage of the sort.
Qsorting N elements costs O(N*lnN), so excluding H elements from the
sort reduces the cost by at least O(H*lnN). The merge step costs O(N)
plus some (<=50%) more memory, unless someone knows a fast in-place
merge. So depending on the constant factors involved there might be a
usable solution.
I've been playing with some numbers and assuming the constant factors
to be equal for all the O()'s this method starts to pay off at H for N 20 100 130 10008000 100000
ServusManfred