From owner-freebsd-hackers@freebsd.org Sat Nov 26 19:51:33 2016 Return-Path: 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 93A98C574E8 for ; Sat, 26 Nov 2016 19:51:33 +0000 (UTC) (envelope-from m.e.sanliturk@gmail.com) Received: from mail-yw0-x233.google.com (mail-yw0-x233.google.com [IPv6:2607:f8b0:4002:c05::233]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 484B21AEA for ; Sat, 26 Nov 2016 19:51:33 +0000 (UTC) (envelope-from m.e.sanliturk@gmail.com) Received: by mail-yw0-x233.google.com with SMTP id a10so85946349ywa.3 for ; Sat, 26 Nov 2016 11:51:33 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=poaAatZsQKPwa6JhbCqyETERRR8kAj905scUOC0Yu4c=; b=woWoPY53SYTTUu6paARrWPOQVX1YzTaL9DXuTR90xJgosC4RHsRbIM4pPmnqKQvqIe c8THam+GAXHh3ziObN6SfGku9dhWqM85RLjKO9sAVzW9XWjUWhM2Q/w+dAbCezhOgewT qn+Ptp/otvQ2dAbAkahAjforWVDRpBCzcWhDobqA2J9QpCy6vMCApjOlomQm4Beyi3yi cltgtSNb46oW0l0yQSibgav/7V9O5XjyXoKDxHNnWY/eI72XLiRPWMQNlxghdUJ1AydP ALv9dYhIeVkZg+bXgIaWm7kpU+D2ClOPWtTFTcAQ/s7DsxeFVgun2dxMoXpsHHDCebyi WFLA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=poaAatZsQKPwa6JhbCqyETERRR8kAj905scUOC0Yu4c=; b=imAsSt92yx5p0iOGuyE7UqBnLHvu8abzqqONtTkb5TtWIhA/4m3uzoxPc6GZ11FT6P RVZSNIZ+Fi8mqWJXpLqicOjX7QDZxfq83UgnQoNdLQmBEkdIzfXVbBGePofrjNX3uAEt KZ76kFC6IidrZ0VnqtMNyNszc1N5jzQj1m9kLtj5h2I94fllvX/MrHO1ckRXUAciQXjj rgXj5fcyI1AQQUlMKbCtbKIpwNC88frtwExuuAtSEbQaTddkh/1dkDd47u93qb6ohKUg 5bselH8CsP7b+yTx4zGIHWI0MCBzHugd/Fe4GOlj39i3yd+cHNaFOr+ZRiaMeJFGNc52 ESlg== X-Gm-Message-State: AKaTC021sMD2+wOyxTetyCbvE6y6UcCu/V3DronR36jy8UJ3Xfez1EAnW7CsROmnR8mF1UTngNr4c8CIPCkPlg== X-Received: by 10.129.206.2 with SMTP id t2mr19625565ywi.181.1480189892347; Sat, 26 Nov 2016 11:51:32 -0800 (PST) MIME-Version: 1.0 Received: by 10.37.170.67 with HTTP; Sat, 26 Nov 2016 11:51:31 -0800 (PST) In-Reply-To: References: <0bfb49b0-5d24-2766-6982-b4e49b0d5e81@selasky.org> From: Mehmet Erol Sanliturk Date: Sat, 26 Nov 2016 11:51:31 -0800 Message-ID: Subject: Re: qsort switching to insertsort To: =?UTF-8?Q?Arne_Dag_Fidjest=C3=B8l?= Cc: Tristan Verniquet , Hans Petter Selasky , freebsd hackers Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Content-Filtered-By: Mailman/MimeDel 2.1.23 X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 26 Nov 2016 19:51:33 -0000 On Sat, Nov 26, 2016 at 9:14 AM, Arne Dag Fidjest=C3=B8l = wrote: > > > On 26 Nov 2016, at 15:35, Mehmet Erol Sanliturk > wrote: > > > > In quick sort , it is necessary to check worst case and switch to anoth= er > > 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 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