From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Thread: 103376,f6c360ce344b2364
X-Google-NewGroupId: yes
X-Google-Attributes: gida07f3367d7,domainid0,public,usenet
X-Google-Language: ENGLISH,ASCII-7-bit
Received: by 10.68.193.129 with SMTP id ho1mr23701494pbc.8.1340221530065;
        Wed, 20 Jun 2012 12:45:30 -0700 (PDT)
Path: 
 l9ni7pbj.0!nntp.google.com!news1.google.com!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
From: ggsub@pragmada.co.cc
Newsgroups: comp.lang.ada
Subject: Re: My Invention of "Bug Sort".
Date: Wed, 20 Jun 2012 12:45:29 -0700 (PDT)
Organization: http://groups.google.com
Message-ID: <05ea54c4-d73e-41a5-b666-50614ba33013@googlegroups.com>
References: <3852c348-a728-44ed-b065-c8a596c1e235@googlegroups.com>
 <698085ff-6ca3-4a0e-b963-11bdcf11e6b5@googlegroups.com>
 <5c5aa9d4-fcfe-46fb-9b85-762518651455@googlegroups.com>
NNTP-Posting-Host: 184.20.201.198
Mime-Version: 1.0
X-Trace: posting.google.com 1340221529 20671 127.0.0.1 (20 Jun 2012 19:45:29
 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Wed, 20 Jun 2012 19:45:29 +0000 (UTC)
In-Reply-To: <5c5aa9d4-fcfe-46fb-9b85-762518651455@googlegroups.com>
Complaints-To: groups-abuse@google.com
Injection-Info: glegroupsg2000goo.googlegroups.com;
 posting-host=184.20.201.198;
 posting-account=uInPWgoAAAD9VvUJDc0jNwDhBg_137JZ
User-Agent: G2/1.0
Content-Type: text/plain; charset=ISO-8859-1
Date: 2012-06-20T12:45:29-07:00
List-Id: <comp.lang.ada>

On Wednesday, June 20, 2012 1:32:44 AM UTC-7, Austin Obyrne wrote:
> 
> I think this sums it up completely. I realise now that this is a can of worms when taken as general sort program and probably no better than any other.

Since it takes linear time O(B), it's faster than any comparison sort, the best of which are O(N log N).

> Question: In a real world situation could this sort mechanism be done by a 'tasking' package in Ada. 

Parallelizing this algorithm is straightforward; there's a discussion of it in the Wikipedia page on counting sort.

--
Jeff Carter
jrcarter commercial-at-sign acm (period | full stop) org