qsort switching to insertsort

[Tristan Verniquet]

From: Mehmet Erol Sanliturk <m.e.sanliturk at gmail.com>
Sent: Sunday, 27 November 2016 5:51 AM
To: Arne Dag Fidjestøl
Cc: Tristan Verniquet; Hans Petter Selasky; freebsd hackers
Subject: Re: qsort switching to insertsort



On Sat, Nov 26, 2016 at 9:14 AM, Arne Dag Fidjestøl <adf at idi.ntnu.no> wrote:

> On 26 Nov 2016, at 15:35, Mehmet Erol Sanliturk <m.e.sanliturk at gmail.com> wrote:
>
> In quick sort , it is necessary to check worst case and switch to another
> sort method if it is detected .
> When this is not done , end result is stack overflow , etc . , but not
> success .
> Therefore , it is not possible to eliminate an alternative sort method .

I you sort the smaller partition recursively first, and then sort the larger partition either by tail recursion or iteration, you will only consume O(log n) of stack, so stack overflow needn’t be an issue, regardless of the input.

-adf



Important problem is caused by almost sorted values . Myself , I am counting the sorted elements first , if they exceed a large percentage of number of all elements , then I am switching to an alternative sort , otherwise a quick sort is used .  This is for a simple application .

In an operating system , more complex algorithms may be more useful .


Mehmet Erol Sanliturk

---

It can still trigger with completely unsorted data in the top and bottom half, as long as it chooses the middle value for the pivot. The main reason nearly sorted data is vulnerable is that it is more likely to match these conditions, and more likely to happen in real life situations.

But this is why i don't really consider it an "edge" case, there would be a whole class of situations (like the one we had) where it would be very likely to trigger with very bad side effects.

Maybe, does anyone continue to use FreeBSD qsort while being aware of this implementation detail? Under what conditions/assurances?

Does anyone use FreeBSDs qsort because of this feature?

Tristan
________________________________
From: Mehmet Erol Sanliturk <m.e.sanliturk at gmail.com>
Sent: Sunday, 27 November 2016 5:51:31 AM
To: Arne Dag Fidjestøl
Cc: Tristan Verniquet; Hans Petter Selasky; freebsd hackers
Subject: Re: qsort switching to insertsort



On Sat, Nov 26, 2016 at 9:14 AM, Arne Dag Fidjestøl <adf at idi.ntnu.no<mailto:adf at idi.ntnu.no>> wrote:

> On 26 Nov 2016, at 15:35, Mehmet Erol Sanliturk <m.e.sanliturk at gmail.com<mailto:m.e.sanliturk at gmail.com>> wrote:
>
> In quick sort , it is necessary to check worst case and switch to another
> sort method if it is detected .
> When this is not done , end result is stack overflow , etc . , but not
> success .
> Therefore , it is not possible to eliminate an alternative sort method .

I you sort the smaller partition recursively first, and then sort the larger partition either by tail recursion or iteration, you will only consume O(log n) of stack, so stack overflow needn’t be an issue, regardless of the input.

-adf



Important problem is caused by almost sorted values . Myself , I am counting the sorted elements first , if they exceed a large percentage of number of all elements , then I am switching to an alternative sort , otherwise a quick sort is used .  This is for a simple application .

In an operating system , more complex algorithms may be more useful .


Mehmet Erol Sanliturk