Which is better code for implementing quicksort? This is how I used to implement quicksort:

def quickSort(alist):
   quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
   if first&lt;last:

       splitpoint = partition(alist,first,last)

       quickSortHelper(alist,first,splitpoint-1)
       quickSortHelper(alist,splitpoint+1,last)


def partition(alist,first,last):
   pivotvalue = alist[first]

   leftmark = first+1
   rightmark = last

   done = False
   while not done:

       while leftmark &lt;= rightmark and alist[leftmark] &lt;= pivotvalue:
           leftmark = leftmark + 1

       while alist[rightmark] &gt;= pivotvalue and rightmark &gt;= leftmark:
           rightmark = rightmark -1

       if rightmark &lt; leftmark:
           done = True
       else:
           temp = alist[leftmark]
           alist[leftmark] = alist[rightmark]
           alist[rightmark] = temp

   temp = alist[first]
   alist[first] = alist[rightmark]
   alist[rightmark] = temp


   return rightmark

alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)


But recently I have come across this way of implementing quicksort:


def quickSort(L):  
    if L == []: return []  
    return     quickSort([x for x in L[1:] if x&lt; L[0]]) + L[0:1] + quickSort([x for x in L[1:] if x&gt;=L[0]])

a = [54,26,93,17,77,31,44,55,20]

a = quickSort(a)
print(a)



Which implementation is better in terms of memory usage and time complexity?
Both are very similar - list of 100000 random int elements (from 0 to 100000) was sorted in (average time taken from 10 tries):

#1st implementation
Average time:
Random: 0.4825087092408925

#2nd implementation
Average time:
Random: 0.48071902671725464


That being said, both implementations aren't good. A lot of people forget to include shuffling at the beginning of quicksort and it has really long call stack. When I added some data sets:

data_sets = {'Sorted': [x for x in range(how_many)],
             'Reverse': list(reversed([x for x in range(how_many)])),
             'Random': [random.randint(0, how_many) for x in range(how_many)],
             'A lot of equal keys': [x if x % 2 else 0 for x in range(how_many)],
             'Same keys': [1] * how_many}


I managed to sort data which was 900 elements in length (more than that gave me recursion error) and performance took a big hit in case of sorted / reversed / lot of equal keys data:

Average time:
Same keys: 0.061130084848424526
Sorted: 0.060439534806328445
A lot of equal keys: 0.032078340092241295
Reverse: 0.06125047935425505
Random: 0.0030011541824106593


EDIT:
As per suggestion in comment, I ran quicksort (with shuffling) and compared it with list.sort(). quicksort was first, then I ran list.sort(), waited for a bit and re-run with reversed order - times were very close in both cases.

100000 items, 10 tries. Tests were ran on my laptop, so hardware is different than in original post.

#QUICKSORT
Average time:
A lot of equal keys: 0.9257455763466982
Sorted: 1.605769951669822
Reverse: 1.5616443986206265
Random: 1.471783668415066
Same keys: 0.28260723572820756

#SORT
Average time:
A lot of equal keys: 0.025862182302070193
Sorted: 0.004639602319800995
Reverse: 0.004855047960047393
Random: 0.10296205183842413
Same keys: 0.0034818929132122674