Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S261527AbVAXQ4g (ORCPT ); Mon, 24 Jan 2005 11:56:36 -0500 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S261492AbVAXQxL (ORCPT ); Mon, 24 Jan 2005 11:53:11 -0500 Received: from clock-tower.bc.nu ([81.2.110.250]:50838 "EHLO lxorguk.ukuu.org.uk") by vger.kernel.org with ESMTP id S261533AbVAXQuj (ORCPT ); Mon, 24 Jan 2005 11:50:39 -0500 Subject: Re: [patch 1/13] Qsort From: Alan Cox To: Jesper Juhl Cc: Andi Kleen , Felipe Alfaro Solana , Trond Myklebust , Linux Kernel Mailing List , Buck Huppmann , Neil Brown , Andreas Gruenbacher , "Andries E. Brouwer" , Andrew Morton , Olaf Kirch In-Reply-To: References: <20050122203326.402087000@blunzn.suse.de> <20050122203618.962749000@blunzn.suse.de> <20050123044637.GA54433@muc.de> Content-Type: text/plain Content-Transfer-Encoding: 7bit Message-Id: <1106512289.6148.31.camel@localhost.localdomain> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.4.6 (1.4.6-2) Date: Mon, 24 Jan 2005 15:45:10 +0000 Sender: linux-kernel-owner@vger.kernel.org X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 772 Lines: 16 On Sul, 2005-01-23 at 05:05, Jesper Juhl wrote: > On Sun, 23 Jan 2005, Andi Kleen wrote: > Even with large data sets that are mostly unsorted shell sorts performance > is close to qsort, and there's an optimization that gives it O(n^(3/2)) > runtime (IIRC), and another nice property is that it's iterative so it > doesn't eat up stack space (as oposed to qsort which is recursive and eats > stack like ****)... qsort also has bad worst case performance which matters if you are sorting data provided by a hostile source. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/