Sorting troubles

[seyensubs at yahoo.com]

On May 15, 5:35 am, Steven D'Aprano
<ste... at REMOVE.THIS.cybersource.com.au> wrote:
> On Mon, 14 May 2007 09:49:56 -0700, Thomas Nelson wrote:
> > The thing is that [x for x in List[1:]...] is a brand new list created
> > by iterating over the old one.
> > How about:
> > qSortHelp(List):
> >     newlist = qSort(List)
> >     for i, val in enumerate(newlist):
> >         List[i] = val
> > You have to iterate over one more time, but this sorts the list in
> > place.
>
> A better way of spelling that would be:
>
> def qSortHelp(List):
>     List[:] = qSort(List)
>     return List
>
> but the helper function is redundant, as it is easy enough to make the
> qSort function behave the same way. We can also make the code a smidgen
> more concise by reversing the sense of the test at the start of the code:
>
> def qSort(List):
>     if List:
>         List[:] = qSort([x for x in List[1:] if x< List[0]]) \
>         + List[0:1] + qSort([x for x in List[1:] if x>=List[0]])
>     return List
>
> --
> Steven.

Ah, I see, just slicing it like that.. nice!
But after doing some timing tests, the version that's in place and
using partitions is about twice faster than the non hybrid qSort.
The hybrid one, with insertionsSort used for smaller lists works
faster, but in a weird way. When given lists of 2000, the best bet to
is to set the threshold to 14, but when given a list of 40000, 14 is
slow, but a threshold of 200(less or more is slower, again) makes it
about 8 times faster than a normal qSort, and 4 times faster than an
in-place qSort, using a self -defined partitioning alg.

Making a hybrid out of the in-place partitioned qSort makes it a bit
faster, but not by much compared to the other hybrid which uses list
comprehensions.

Teach said that the optimal threshold in hybrids is 14-16, but guess
he wasn't so right after all =\\ The overhead of using insertion sort
on a longer list turns out to be faster than just piling on
recursions, when confronted with bigger lists.

I should probably try and make it iterative now, see how it goes.
Gonna need a stack though, I think.

Thanks for all the answers up to now! :)