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: > > 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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?B8ECCF6B-6477-441B-87F1-0DB3B36F828E>