Path: csiph.com!usenet.pasdenom.info!news.etla.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path: <python-python-list@m.gmane.org>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.059
X-Spam-Evidence: '*H*': 0.88; '*S*': 0.00; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'wrote': 0.14; 'pair.': 0.16; 'received:80.91.229.3': 0.16; 'received:plane.gmane.org': 0.16; 'subject:Sort': 0.16; 'input': 0.22; 'example': 0.22; 'header:X -Complaints-To:1': 0.27; 'subject:) ': 0.29; 'url:mailman': 0.30; 'lists': 0.32; 'url:python': 0.33; 'subject:time': 0.33; 'no,': 0.35; 'sequence': 0.36; 'subject:one': 0.36; 'url:listinfo': 0.36; 'url:org': 0.36; 'so,': 0.37; 'two': 0.37; 'list': 0.37; 'to:addr :python-list': 0.38; 'to:addr:python.org': 0.39; 'received:org': 0.40; 'space': 0.40; 'url:mail': 0.40; 'how': 0.40; 'show': 0.63; 'here': 0.66; 'complexity': 0.84; 'received:myvzw.com': 0.84; 'subject:space': 0.84; 'thoroughly': 0.91
X-Injected-Via-Gmane: http://gmane.org/
To: python-list@python.org
From: Dave Angel <davea@davea.name>
Subject: Re: Sort one sequence by O(n) in time and O(1) in space
Date: Sun, 9 Feb 2014 22:00:56 -0500 (EST)
Organization: news.gmane.org
References: <ae372652-0f1c-4d79-82db-a522eb592579@googlegroups.com> <mailman.6582.1391949589.18130.python-list@python.org> <76182aa9-75bc-446d-87ea-9545fe7e2a8f@googlegroups.com>
X-Gmane-NNTP-Posting-Host: 200.sub-70-208-140.myvzw.com
X-Newsreader: PiaoHong Usenet NewsReaders 1.36
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.6609.1392001209.18130.python-list@python.org>
Lines: 19
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1392001209 news.xs4all.nl 2830 [2001:888:2000:d::a6]:46020
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:65797

 Wesley <nispray@gmail.com> Wrote in message:
> 
>> > here is input sequence like a1,a2,...,an,b1,b2,...,bn ，the 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? 
> 
> [Wesley] No, not sorted yet..
> -- 
> https://mail.python.org/mailman/listinfo/python-list
> 

Then supply some example lists and show the result you want. So
 far, your description is thoroughly ambiguous.

-- 
DaveA