Quick sort implementation in python

[bearophileHUGS at lycos.com]

Alex Snast:
> However i have no idea how to access the values of a data structure that doesn't allow random access.<

Well, a sorting algorithm can work in-place, sorting the position of
the items inside the given collection, or it can create a new data
structure with the items (in Python all items are references). If the
output of the sorting algorithm is an array (that is a python list),
and the input isn't a list, then you can list-fy your input data and
then sort that list in-place, and return it.

Like this

def mysort(any_iterable):
   data = list(any_iterable)
   # sort data...
   return data

If the input is a list, you can sort it in place.

Finally you may want to return other kinds of collections, like
sorting a linked list and returning it (you can create a chain of
nested lists, and then sort them with a merge sort), but in Python
that's not much common.

Bye,
bearophile