## Re: Re: Which qsort is used

From: Manfred Koizar Tom Lane "Dann Corbit" , "Qingqing Zhou" , "Bruce Momjian" , "Luke Lonergan" , "Neil Conway" , pgsql-hackers(at)postgresql(dot)org Re: Re: Which qsort is used 2005-12-22 00:43:34 odqjq1tv6cb77ri4df0aehqal8o0ljtkar@4ax.com (view raw or whole thread) 2005-12-17 01:17:56 from "Dann Corbit"  2005-12-17 05:03:25 from Tom Lane   2005-12-22 00:43:34 from Manfred Koizar    2005-12-22 07:01:00 from Martijn van Oosterhout     2005-12-22 21:58:31 from Manfred Koizar pgsql-hackers
```On Sat, 17 Dec 2005 00:03:25 -0500, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)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      1000
8000    100000
Servus
Manfred

```

### pgsql-hackers by date

 Next: From: Jim C. Nasby Date: 2005-12-22 00:54:08 Subject: Re: Automatic function replanning Previous: From: Tom Lane Date: 2005-12-22 00:07:23 Subject: Re: Unsplitting btree index leaf pages