From owner-freebsd-hackers@freebsd.org  Sat Nov 26 17:14:13 2016
Return-Path: <owner-freebsd-hackers@freebsd.org>
Delivered-To: freebsd-hackers@mailman.ysv.freebsd.org
Received: from mx1.freebsd.org (mx1.freebsd.org
 [IPv6:2001:1900:2254:206a::19:1])
 by mailman.ysv.freebsd.org (Postfix) with ESMTP id 20C0CC579D8
 for <freebsd-hackers@mailman.ysv.freebsd.org>;
 Sat, 26 Nov 2016 17:14:13 +0000 (UTC) (envelope-from adf@idi.ntnu.no)
Received: from hylle05.itea.ntnu.no (hylle05.itea.ntnu.no
 [IPv6:2001:700:300:3::225])
 (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits))
 (Client did not present a certificate)
 by mx1.freebsd.org (Postfix) with ESMTPS id D6F121BF2
 for <freebsd-hackers@freebsd.org>; Sat, 26 Nov 2016 17:14:12 +0000 (UTC)
 (envelope-from adf@idi.ntnu.no)
Received: from localhost (localhost [127.0.0.1])
 by hylle05.itea.ntnu.no (Postfix) with ESMTP id A147A907151;
 Sat, 26 Nov 2016 18:14:08 +0100 (CET)
X-Virus-Scanned: Debian amavisd-new at hylle05.itea.ntnu.no
Received: from [10.10.10.166] (unknown [109.201.137.162])
 (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits))
 (No client certificate requested) (Authenticated sender: adf)
 by hylle05.itea.ntnu.no (Postfix) with ESMTPSA id CE8EE907134;
 Sat, 26 Nov 2016 18:14:07 +0100 (CET)
Subject: Re: qsort switching to insertsort
Mime-Version: 1.0 (Mac OS X Mail 9.3 \(3124\))
Content-Type: text/plain; charset=utf-8
From: =?utf-8?Q?Arne_Dag_Fidjest=C3=B8l?= <adf@idi.ntnu.no>
In-Reply-To: <CAOgwaMvUE+K==OE3zkpfpXa5kBC1YT4JAUVhujxEt9PcHXgqTw@mail.gmail.com>
Date: Sat, 26 Nov 2016 18:14:06 +0100
Cc: Tristan Verniquet <tris_vern@hotmail.com>,
 Hans Petter Selasky <hps@selasky.org>,
 freebsd hackers <freebsd-hackers@freebsd.org>
Content-Transfer-Encoding: quoted-printable
Message-Id: <B8ECCF6B-6477-441B-87F1-0DB3B36F828E@idi.ntnu.no>
References: <ME1PR01MB0546A92343D712D8439B299C83880@ME1PR01MB0546.ausprd01.prod.outlook.com>
 <0bfb49b0-5d24-2766-6982-b4e49b0d5e81@selasky.org>
 <ME1PR01MB0546D041DC160763C5D3689883880@ME1PR01MB0546.ausprd01.prod.outlook.com>
 <CAOgwaMvUE+K==OE3zkpfpXa5kBC1YT4JAUVhujxEt9PcHXgqTw@mail.gmail.com>
To: Mehmet Erol Sanliturk <m.e.sanliturk@gmail.com>
X-Mailer: Apple Mail (2.3124)
X-Mailman-Approved-At: Sat, 26 Nov 2016 17:45:21 +0000
X-BeenThere: freebsd-hackers@freebsd.org
X-Mailman-Version: 2.1.23
Precedence: list
List-Id: Technical Discussions relating to FreeBSD
 <freebsd-hackers.freebsd.org>
List-Unsubscribe: <https://lists.freebsd.org/mailman/options/freebsd-hackers>, 
 <mailto:freebsd-hackers-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-hackers/>
List-Post: <mailto:freebsd-hackers@freebsd.org>
List-Help: <mailto:freebsd-hackers-request@freebsd.org?subject=help>
List-Subscribe: <https://lists.freebsd.org/mailman/listinfo/freebsd-hackers>, 
 <mailto:freebsd-hackers-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Sat, 26 Nov 2016 17:14:13 -0000


> 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=