From owner-freebsd-hackers@freebsd.org Sun Nov 27 13:00:27 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 A88EEC54AA9 for ; Sun, 27 Nov 2016 13:00:27 +0000 (UTC) (envelope-from tris_vern@hotmail.com) Received: from COL004-OMC3S2.hotmail.com (col004-omc3s2.hotmail.com [65.55.34.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (Client CN "*.outlook.com", Issuer "Microsoft IT SSL SHA2" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 6F3D41A38 for ; Sun, 27 Nov 2016 13:00:27 +0000 (UTC) (envelope-from tris_vern@hotmail.com) Received: from AUS01-SY3-obe.outbound.protection.outlook.com ([65.55.34.136]) by COL004-OMC3S2.hotmail.com over TLS secured channel with Microsoft SMTPSVC(7.5.7601.23008); Sun, 27 Nov 2016 04:59:21 -0800 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=hotmail.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version; bh=5GxVU7tT5LHfXVHZAfvTclxYBuRaS62GAkELDxSz0iw=; b=QqxUVdBT1OYX9mjcYFAwrwGNLr1jgAoiw0EzkTtRIFnDanVKUJfx7fzLyydKfZY/i77Z2dqYzK/FylIgeL2umCkRzCbUIPSYeNwyndBRJHSqv8SF7ZmLLx4R5ydJuqg9wZGUQSHt7gYPRWY6/otUimQAYuxa3C0phiWLPpmLa1vdskM/7H2fOEPSktb8NL4Pm/xwQIWGByi7dUH/eAEYcXGaUjB6nTSYU/U/XlvCuXtxlS0x1VukVXQqr5Sq2bXLmxhg9dXx4TkLq69VaazguVMimMb01CSRa16EQl1IOvczKNoAMYrdFiK24DFaSNzDKBFFGcD31GErjn9lsqC3dg== Received: from SY3AUS01FT007.eop-AUS01.prod.protection.outlook.com (10.152.234.53) by SY3AUS01HT008.eop-AUS01.prod.protection.outlook.com (10.152.234.106) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P384) id 15.1.734.4; Sun, 27 Nov 2016 12:59:18 +0000 Received: from ME1PR01MB0546.ausprd01.prod.outlook.com (10.152.234.55) by SY3AUS01FT007.mail.protection.outlook.com (10.152.234.63) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P384) id 15.1.734.4 via Frontend Transport; Sun, 27 Nov 2016 12:59:17 +0000 Received: from ME1PR01MB0546.ausprd01.prod.outlook.com ([10.162.68.22]) by ME1PR01MB0546.ausprd01.prod.outlook.com ([10.162.68.22]) with mapi id 15.01.0734.014; Sun, 27 Nov 2016 12:59:17 +0000 From: Tristan Verniquet To: Mitchell , "freebsd-hackers@freebsd.org" Subject: Re: qsort switching to insertsort Thread-Topic: qsort switching to insertsort Thread-Index: AQHSR8zfjghRy3NqhkaB3zSchVE3aKDrFm4AgAAXcRqAACdOgIAALDUAgAAr+4CAAIhjtYAAkRUAgAADM7s= Date: Sun, 27 Nov 2016 12:59:17 +0000 Message-ID: References: , <2066156.rDbTD5n9LR@daa860> In-Reply-To: <2066156.rDbTD5n9LR@daa860> Accept-Language: en-AU, en-US Content-Language: en-AU X-MS-Has-Attach: X-MS-TNEF-Correlator: authentication-results: wyatt672earp.force9.co.uk; dkim=none (message not signed) header.d=none;wyatt672earp.force9.co.uk; dmarc=none action=none header.from=hotmail.com; x-incomingtopheadermarker: OriginalChecksum:; UpperCasedChecksum:; SizeAsReceived:7673; Count:39 x-ms-exchange-messagesentrepresentingtype: 1 x-tmn: [+J0qG/f7UT46Xos8hjvdUNvdJOLzPDxE] x-incomingheadercount: 39 x-eopattributedmessage: 0 x-microsoft-exchange-diagnostics: 1; SY3AUS01HT008; 5:Rzr1d0Q5lJ70gId8bnH6jd0FHqRUNgUg8neWndraWfgr8BkfXfbydcum/Ln86/V2oLtW2awDcCygI7VXWxHNylKfOGWd/YvsAvy12MArLO3ODmQduiRdGSBwCv8W2ISzfhlDvmAmK2MAx5lpGUYWgDoeaPtfkKiXQYzMLaZGlo8=; 24:sUenJ21msZ7Z9SQqKIn1W7al8AM3z0l7HENw0yf9DPF/Ye9RM+utketP0zGlMhRNdWqOueJnO1o1EAmzrKVrcLTQxYEEK2LvBFe7RW/nPLQ=; 7:SxVdgL0tvNfmee35BwFVfuy5hIo9gZJwqbO7rZfiObBI0YWz7z7kB44DAfblmK8ZrtYKwgddL6sOEsvzHbLRWMXEZI44AnC2tPPxVZHlthlhCxU3vckdFYRw12nATPGbgUdXZpDsg4SZqRyxF4qpvZksXFylS5M5xphFAe/oGB/e3XlRY05KMINmHxA1Syc23BMQ/O1YMzYAIEODGR0y4xfSrK0sm7fwk4Gh/NC6P3X2kGGYva6Fde17ZHEHEsFifbAV/WUZOp9MTh4znzXDTbej0KzVpw6mEOIMH335UGAw+QwZ3Z2cX9akZK2/y/FVXQkJUihXobj0UtNL2V105p+8JX0f8rj6rsT7zIo/pfw= x-forefront-antispam-report: EFV:NLI; SFV:NSPM; SFS:(10019020)(98900003); DIR:OUT; SFP:1102; SCL:1; SRVR:SY3AUS01HT008; H:ME1PR01MB0546.ausprd01.prod.outlook.com; FPR:; SPF:None; LANG:en; x-ms-office365-filtering-correlation-id: fcb29d4a-1cdd-42f5-ecf3-08d416c5328e x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(22001)(1601124038)(1603103113)(1603101340)(1601125047); SRVR:SY3AUS01HT008; x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(432015012)(82015046); SRVR:SY3AUS01HT008; BCL:0; PCL:0; RULEID:; SRVR:SY3AUS01HT008; x-forefront-prvs: 0139052FDB spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: hotmail.com X-MS-Exchange-CrossTenant-originalarrivaltime: 27 Nov 2016 12:59:17.7077 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Internet X-MS-Exchange-CrossTenant-id: 84df9e7f-e9f6-40af-b435-aaaaaaaaaaaa X-MS-Exchange-Transport-CrossTenantHeadersStamped: SY3AUS01HT008 X-OriginalArrivalTime: 27 Nov 2016 12:59:21.0557 (UTC) FILETIME=[124AD850:01D248AE] 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: Sun, 27 Nov 2016 13:00:27 -0000 > From: owner-freebsd-hackers@freebsd.org on behalf of Mitchell > Sent: Sunday, 27 November 2016 10:38 PM > To: freebsd-hackers@freebsd.org > Subject: Re: qsort switching to insertsort > =A0 >=A0 > In "Numerical Recipes" (Press, Teukolsky, Vetterling & Flannery) the=A0 > Partitioning Element chosen is the median of the First, Middle & Last. Th= ey=A0 > mention other techniques too. The method used in FreeBSD qsort is the ninther approach. Ie the med3 of 3 = med3's from the start, middle and end of the partition. pm =3D (char *)a + (n / 2) * es; if (n > 7) { =A0 =A0 =A0 =A0pl =3D a; =A0 =A0 =A0 =A0pn =3D (char *)a + (n - 1) * es; =A0 =A0 =A0 =A0if (n > 40) { =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0d =3D (n / 8) * es; =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0pl =3D med3(pl, pl + d, pl + 2 * d, cmp, thu= nk); =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0pm =3D med3(pm - d, pm, pm + d, cmp, thunk); =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0pn =3D med3(pn - 2 * d, pn - d, pn, cmp, thu= nk); =A0 =A0 =A0 =A0} =A0 =A0 =A0 =A0pm =3D med3(pl, pm, pn, cmp, thunk); } swap(a, pm); https://en.wikipedia.org/wiki/Median#Ninther So it is very hard to hit a bad pivot case with everyday data, but not that= unrealistic to hit the insertsort (swap_cnt =3D=3D 0) case with certain se= ts of data. Tristan =