A little taste about quick sort

This week, Professor used a algorithm called quick sort to demonstrate the usage of recursion. The idea of quick sort is basically a divide and conquer algorithm. Basically, it requires us to find a pivot point in an array. And then, we loop for the whole array and compare its value to this pivot point. If it is less or equal to the pivot value, we put it to the left of the pivot point, else we put it to its right side. Note that we maintain the original order when we compare each value because we loop from left to the right. So after this first step we can say the part in the left of the pivot is surely less or equal to the pivot and the right part is greater than the pivot.

Now, we have divide the whole array into three parts, left part of the pivot, pivot and the right part of the pivot. We know that at this level, this three part is already sorted. I mean the values in each area is sorted in a macro level. But within each part, the values might not be sorted. For this reason, we notice that the left part and the right part can be treated as a new array and we can use the same method to keep dividing it into smaller parts until we reach the bottom of the array. That is where we can apply recursion.

# simple quick sort


def quick_sort(L):
    ''' (list) -> list

    Return a list containing the same elements as L in ascending order.

    >>> quick_sort([])
    []
    >>> quick_sort([5])
    [5]
    >>> import random
    >>> L = [1, 2, 3, 4, 5, 6, 7]
    >>> random.shuffle(L)
    >>> quick_sort(L)
    [1, 2, 3, 4, 5, 6, 7]
    '''
    if len(L) < 2: # there's nothing to sort
        return L
    else:
        return (quick_sort([x for x in L if x < L[0]]) + 
                [L[0]] + 
                quick_sort([x for x in L[1:] if x >= L[0]]))

here is the code from professor's lecture note. Note the recursion part 
return (quick_sort([x for x in L if x < L[0]]) + 
                [L[0]] + 
                quick_sort([x for x in L[1:] if x >= L[0]]))

we keep calling function quick_sort recursively to get the sorted list. But here, 

we always choose the first element of the array as the pivot point. If we encounter

a sorted list which means the first element is the smallest one, then we have a 

very unbalanced pivot list and this algorithm will be very slow.