Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!newsfeed.xs4all.nl!newsfeed4a.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.020 X-Spam-Evidence: '*H*': 0.96; '*S*': 0.00; 'memory.': 0.07; 'modifying': 0.07; 'iterate': 0.09; 'cc:addr:python-list': 0.11; 'def': 0.12; 'from:addr:rosuav': 0.16; 'from:name:chris angelico': 0.16; 'iterates': 0.16; 'once.': 0.16; 'operation,': 0.16; 'pair.': 0.16; 'pythonic': 0.16; 'skip:[ 40': 0.16; 'subject:Sort': 0.16; 'wrote:': 0.18; 'feb': 0.22; 'input': 0.22; 'cc:addr:python.org': 0.22; 'cc:2**0': 0.24; 'sort': 0.25; 'defined': 0.27; 'header:In-Reply-To:1': 0.27; 'function': 0.29; 'subject:) ': 0.29; 'message-id:@mail.gmail.com': 0.30; 'gives': 0.31; 'subject:time': 0.33; 'could': 0.34; 'but': 0.35; 'received:google.com': 0.35; 'sequence': 0.36; 'subject:one': 0.36; 'yield': 0.36; 'so,': 0.37; 'two': 0.37; 'list': 0.37; 'list.': 0.37; 'arrange': 0.38; 'pm,': 0.38; 'that,': 0.38; 'space': 0.40; 'how': 0.40; 'above,': 0.60; 'new': 0.61; 'effective': 0.61; 'simply': 0.61; 'kind': 0.63; 'more': 0.64; 'here': 0.66; 'complexity': 0.84; 'subject:space': 0.84; 'to:none': 0.92 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:cc :content-type:content-transfer-encoding; bh=dRPCA63UPDXDlSQTUFdrNr0LSgFM2r7tmix63EN2gww=; b=CPNSyO4c45BMQdLT2dGDf53S+94sYizq95f2HZlgrn9R6FMJXobjUfNuQ1ZN7evpT2 Q/m5ztw0sPVGTPWPLDIEd19JbLp6YCdFe5NRLN99Qf6zgGLU42Q6o9qdyBl9FC8nR8Ui I9aTW4MXz2QF2QetO5oemNocn6NaQvE5Q4h/zicUq7/5fbN78+DYUARQNtAjL40cD8qo 4KwiWj5+82ok6FzsK4OzdZHQ2jY3zqM8JBhRca1ttyOSNsb5T636OykAh5q3WrVbq8iv sviNcEJDuAQjCfJ904msKCaAC1RKn2I5HcvXxFlsvJ9A1rYljGtCjRHR5Qyho1MTaM6E 3C3w== MIME-Version: 1.0 X-Received: by 10.68.108.194 with SMTP id hm2mr31700163pbb.22.1391949579383; Sun, 09 Feb 2014 04:39:39 -0800 (PST) In-Reply-To: References: Date: Sun, 9 Feb 2014 23:39:39 +1100 Subject: Re: Sort one sequence by O(n) in time and O(1) in space From: Chris Angelico Cc: "python-list@python.org" Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable 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: , Newsgroups: comp.lang.python Message-ID: Lines: 26 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1391949589 news.xs4all.nl 2907 [2001:888:2000:d::a6]:58167 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:65749 On Sun, Feb 9, 2014 at 11:13 PM, Wesley wrote: > here is input sequence like a1,a2,...,an,b1,b2,...,bn =EF=BC=8Cthe ax and= bx always exist in pair. So, now, how to change the sequence to a1,b1,...,= an,bn, with time complexity as O(n) and space as O(1). The two halves of the list are already sorted, yes? Then you don't need a sort operation, just a zip. def flip_list(lst): offset =3D len(lst)//2 for i in range(offset): yield lst[i] yield lst[i+offset] start =3D ['a1','a2','a3','a4','b1','b2','b3','b4'] result =3D list(flip_list(start)) print(result) Alternatively, you could arrange this as some kind of swap operation, modifying the list in place, but I think the more Pythonic way will be to create a new list. Note that, with the function defined as I have above, you can iterate over the flipped list without actually coalescing it in memory. That gives effective O(1) space, and it's definitely O(n) time as it simply iterates over the whole list once. ChrisA