Date: Sat, 26 Nov 2016 18:14:06 +0100 From: =?utf-8?Q?Arne_Dag_Fidjest=C3=B8l?= <adf@idi.ntnu.no> To: Mehmet Erol Sanliturk <m.e.sanliturk@gmail.com> Cc: Tristan Verniquet <tris_vern@hotmail.com>, Hans Petter Selasky <hps@selasky.org>, freebsd hackers <freebsd-hackers@freebsd.org> Subject: Re: qsort switching to insertsort Message-ID: <B8ECCF6B-6477-441B-87F1-0DB3B36F828E@idi.ntnu.no> In-Reply-To: <CAOgwaMvUE%2BK==OE3zkpfpXa5kBC1YT4JAUVhujxEt9PcHXgqTw@mail.gmail.com> References: <ME1PR01MB0546A92343D712D8439B299C83880@ME1PR01MB0546.ausprd01.prod.outlook.com> <0bfb49b0-5d24-2766-6982-b4e49b0d5e81@selasky.org> <ME1PR01MB0546D041DC160763C5D3689883880@ME1PR01MB0546.ausprd01.prod.outlook.com> <CAOgwaMvUE%2BK==OE3zkpfpXa5kBC1YT4JAUVhujxEt9PcHXgqTw@mail.gmail.com>
next in thread | previous in thread | raw e-mail | index | archive | help
> On 26 Nov 2016, at 15:35, Mehmet Erol Sanliturk = <m.e.sanliturk@gmail.com> wrote: >=20 > 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=E2=80=99t be an = issue, regardless of the input. -adf=
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?B8ECCF6B-6477-441B-87F1-0DB3B36F828E>