| From: | "Dann Corbit" <DCorbit(at)connx(dot)com> |
|---|---|
| To: | "Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us> |
| Cc: | "Jonah H(dot) Harris" <jonah(dot)harris(at)gmail(dot)com>, <pgsql-hackers(at)postgresql(dot)org>, "Jerry Sievers" <jerry(at)jerrysievers(dot)com> |
| Subject: | Re: qsort, once again |
| Date: | 2006-03-17 00:42:20 |
| Message-ID: | D425483C2C5C9F49B5B7A41F8944154757D688@postal.corporate.connx.com |
| Views: | Raw Message | Whole Thread | Download mbox | Resend email |
| Thread: | |
| Lists: | pgsql-hackers |
> So my feeling is we should just remove the swap_cnt code and return to
> the original B&M algorithm. Being much faster than expected for
> presorted input doesn't justify being far slower than expected for
> other inputs, IMHO. In the context of Postgres I doubt that perfectly
> sorted input shows up very often anyway.
>
> Comments?
Checking for presorted input is O(n).
If the input is random, an average of 3 elements will be tested.
So adding an in-order check of the data should not be too expensive.
I would benchmark several approaches and see which one is best when used
in-place.
| From | Date | Subject | |
|---|---|---|---|
| Next Message | Dann Corbit | 2006-03-17 01:12:35 | Re: qsort, once again |
| Previous Message | Tom Lane | 2006-03-16 23:48:09 | Re: qsort, once again |