Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!newsfeed.xs4all.nl!newsfeed3.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.043 X-Spam-Evidence: '*H*': 0.91; '*S*': 0.00; 'represents': 0.05; 'integers': 0.09; 'pgp': 0.09; 'comparison.': 0.16; 'impractical': 0.16; 'inputs': 0.16; 'positional': 0.16; 'sorting': 0.16; 'sorts': 0.16; 'subject:Sort': 0.16; 'worst': 0.16; 'elements': 0.16; 'wrote:': 0.18; 'bit': 0.19; 'header:User-Agent:1': 0.23; 'algorithms.': 0.24; 'example.': 0.24; 'sort': 0.25; 'order.': 0.26; 'tables': 0.26; 'second': 0.26; 'values': 0.27; 'header:In- Reply-To:1': 0.27; 'to:2**1': 0.27; 'am,': 0.29; 'subject:) ': 0.29; 'thus': 0.29; 'tim': 0.29; 'fine,': 0.31; 'keys': 0.31; 'subject:time': 0.33; 'created': 0.35; 'but': 0.35; 'there': 0.35; 'sequence': 0.36; 'subject:one': 0.36; 'possible': 0.36; 'example,': 0.37; 'operating': 0.37; 'list': 0.37; 'represent': 0.38; 'to:addr:python-list': 0.38; 'short': 0.38; 'to:addr:python.org': 0.39; 'read': 0.60; 'then,': 0.60; 'lower': 0.61; 'range': 0.61; 'real': 0.63; 'such': 0.63; 'field': 0.63; 'to:addr:gmail.com': 0.65; 'within': 0.65; 'world': 0.66; 'ranges': 0.74; 'guaranteed': 0.75; 'complexity': 0.84; 'subject:space': 0.84 Date: Mon, 10 Feb 2014 23:37:26 -0600 From: Tim Daneliuk User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.2.0 MIME-Version: 1.0 Newsgroups: comp.lang.python To: Sturla Molden , python-list@python.org Subject: Re: Sort one sequence by O(n) in time and O(1) in space References: <52f80bca$0$29972$c3e8da3$5496439d@news.astraweb.com> <9671c418-cde8-4857-85ec-52380f8390eb@googlegroups.com> In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Greylist: Sender succeeded SMTP AUTH, not delayed by milter-greylist-4.4.3 (ozzie.tundraware.com [75.145.138.73]); Mon, 10 Feb 2014 23:37:26 -0600 (CST) X-TundraWare-MailScanner-Information: Please contact the ISP for more information X-TundraWare-MailScanner-ID: s1B5bQ5r046300 X-TundraWare-MailScanner: Found to be clean X-TundraWare-MailScanner-From: tundra@tundraware.com X-Spam-Status: No X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Message-ID: Lines: 28 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1392097098 news.xs4all.nl 2842 [2001:888:2000:d::a6]:53559 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:65886 On 02/10/2014 04:20 AM, Sturla Molden wrote: > In general, we cannot sort a sequence in O(n) time. O(n log n) is the lower > bound on the complexity. Only true for sorting that involve comparison. However, sorts that use the values of the inputs as positional keys have a lower bound complexity (omega) of O(n) and a worst case complexity of O(n) and are thus asymptotically optimal. For example, given a range of integers guaranteed to be within the range of j to k (lower to higher), one can created a bit field to represent all possible values of j to k. Then, as values are read in, the corresponding but is set true. You have to process the list of n elements once to read it in, and then a second time to read them out in order. This is a 2n operation which is O(n). For very large ranges of j to k, this is impractical and we resort to things like hashing functions which can perform better than n log n sorting algorithms. But there are lots of real world applications where inputs-as-keys works just fine, such as short dispatch tables in operating systems where the value to be sorted represents a process priority, for example. -- ---------------------------------------------------------------------------- Tim Daneliuk tundra@tundraware.com PGP Key: http://www.tundraware.com/PGP/