Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!news-1.dfn.de!news.dfn.de!news.informatik.hu-berlin.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: Gregory Ewing Newsgroups: comp.lang.python Subject: Re: Sort one sequence by O(n) in time and O(1) in space Date: Tue, 11 Feb 2014 13:19:09 +1300 Lines: 16 Message-ID: References: <52f80bca$0$29972$c3e8da3$5496439d@news.astraweb.com> <9671c418-cde8-4857-85ec-52380f8390eb@googlegroups.com> <433934582413720306.205290sturla.molden-gmail.com@news.gmane.org> <2079199387413737237.368296sturla.molden-gmail.com@news.gmane.org> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Trace: individual.net NI3XM2cnB+5fXfZphCP/wwQzUvRIwjeqVU3VsCR0tGU0J5AIJf Cancel-Lock: sha1:uTdJpd1FwV25urSlbVVbQAW/SZ8= User-Agent: Mozilla Thunderbird 1.0.5 (Macintosh/20050711) X-Accept-Language: en-us, en In-Reply-To: Xref: csiph.com comp.lang.python:65852 Chris Angelico wrote: > mylist = reorder_generator(mylist) > > You can iterate over it, but can't index it. But hey, it complies with > the space/time requirements! Rather than a generator, you could use a view object that rearranges the indices when you access an element. That would comply with the space/time requirements and be indexable as well. Actually it would do better than meet the requirements, since in a sense it would be O(1) in both space and time! -- Greg