Pythonic Quicksort

I am currently revising some basic stuff. Expecting to give a lot of interviews this year.

In the text book QuickSort algorithm the partitioning algorithm isn't very pythonic.
Although the logic is quite simple:

  1. Choose a pivot element
  2. Move that element to such a position such that all elements to its left are smaller than it and everything to it's right is greater than it.
def partition(arr):  
  lesser = []
  greater = []
  equal = []
  pivot = arr[-1]

  for each in arr:
    if each < pivot:
      lesser.append(each)
    elif each == pivot:
      equal.append(each)
    else:
      greater.append(each)
  return lesser + eaual + greater

Quicksort has a recursive appeal to it. After the pivot element is in it's correct position, we need to perform the same logic recursively to the left and the right part of the array.

And when there is only one element in the array, the list is already sorted. That's our base condition.

def quicksort(arr):  
  lesser = []
  greater = []
  equal = []

  if len(arr)>1:
    pivot = arr[-1]

    for each in arr:
      if each < pivot :
        lesser.append(each)
      elif each == pivot:
        equal.append(each)
      else:
        greater.append(each)
    return quicksort(lesser) + equal + quicksort(right)
  else:
    return arr