sorting 1172026 entries

[Chris Rebert]

On Sun, May 6, 2012 at 4:54 PM, Cameron Simpson <cs at zip.com.au> wrote:
> On 06May2012 18:36, J. Mwebaze <jmwebaze at gmail.com> wrote:
> | > for filename in txtfiles:
> | >    temp=[]
> | >    f=open(filename)
> | >    for line in f.readlines():
> | >      line = line.strip()
> | >      line=line.split()
> | >      temp.append((parser.parse(line[0]), float(line[1])))
>
> Have you timed the different parts of your code instead of the whole
> thing?
>
> Specificly, do you know the sort time is the large cost?
>
> I would point out that the loop above builds the list by append(), one
> item at a time. That should have runtime cost of the square of the list
> length, 1172026 * 1172026. Though I've just done this:

Er, what? list.append() is O(1) amortized.
Perhaps you're confusing list.append() with list.insert(), which is indeed O(n)?

Cheers,
Chris