Return-Path: Delivered-To: apmail-hadoop-common-user-archive@www.apache.org Received: (qmail 65204 invoked from network); 28 Feb 2011 12:36:42 -0000 Received: from hermes.apache.org (HELO mail.apache.org) (140.211.11.3) by minotaur.apache.org with SMTP; 28 Feb 2011 12:36:42 -0000 Received: (qmail 76576 invoked by uid 500); 28 Feb 2011 12:36:39 -0000 Delivered-To: apmail-hadoop-common-user-archive@hadoop.apache.org Received: (qmail 76195 invoked by uid 500); 28 Feb 2011 12:36:36 -0000 Mailing-List: contact common-user-help@hadoop.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: common-user@hadoop.apache.org Delivered-To: mailing list common-user@hadoop.apache.org Received: (qmail 76181 invoked by uid 99); 28 Feb 2011 12:36:35 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 28 Feb 2011 12:36:35 +0000 X-ASF-Spam-Status: No, hits=-0.0 required=5.0 tests=RCVD_IN_DNSWL_LOW,SPF_NEUTRAL X-Spam-Check-By: apache.org Received-SPF: neutral (nike.apache.org: 209.85.210.176 is neither permitted nor denied by domain of james@tynt.com) Received: from [209.85.210.176] (HELO mail-iy0-f176.google.com) (209.85.210.176) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 28 Feb 2011 12:36:26 +0000 Received: by iyj12 with SMTP id 12so3694678iyj.35 for ; Mon, 28 Feb 2011 04:36:05 -0800 (PST) Received: by 10.231.39.136 with SMTP id g8mr5391195ibe.99.1298896565103; Mon, 28 Feb 2011 04:36:05 -0800 (PST) Received: from [10.0.1.13] (S01060016cbc5f8b4.cg.shawcable.net [174.0.46.252]) by mx.google.com with ESMTPS id d10sm4563098ibb.12.2011.02.28.04.36.02 (version=TLSv1/SSLv3 cipher=OTHER); Mon, 28 Feb 2011 04:36:03 -0800 (PST) Content-Type: text/plain; charset=us-ascii Mime-Version: 1.0 (Apple Message framework v1082) Subject: Re: why quick sort when spill map output? From: James Seigel In-Reply-To: Date: Mon, 28 Feb 2011 05:36:00 -0700 Content-Transfer-Encoding: quoted-printable Message-Id: <693D29E0-35B5-4E90-99E6-43B05F296F64@tynt.com> References: To: common-user@hadoop.apache.org X-Mailer: Apple Mail (2.1082) X-Virus-Checked: Checked by ClamAV on apache.org Sorting out of the map phase is core to how hadoop works. Are you = asking why sort at all? or why did someone use quick sort as opposed to = _____sort? Cheers James On 2011-02-28, at 3:30 AM, elton sky wrote: > Hello forumers, >=20 > Before spill the data in kvbuffer to local disk in map task, k/v are > sorted using quick sort. The complexity of quick sort is O(nlogn) and > worst case is O(n^2). > Why using quick sort? >=20 > Regards