The partitioning step is very important in understanding the implementation of the quick sort algorithm, so we will start with an examination of implementing the partitioning first.

Let's look at another example to understand the implementation. Consider the following list of integers. We shall partition this list using the partition function, as follows:

Consider the following code for this:

     def partition(unsorted_array, first_index, last_index): 

        pivot = unsorted_array[first_index] 
        pivot_index = first_index 
        index_of_last_element = last_index 

        less_than_pivot_index = index_of_last_element 
        greater_than_pivot_index = first_index + 1 
        ...

The partition function receives, as its parameters, the indices of the first and last elements of the array that we need to partition. 

The value of the pivot is stored in the pivot variable, while its index is stored in pivot_index. We are not using unsorted_array[0], because when the unsorted array parameter is called with a segment of an array, index 0 will not necessarily point to the first element in that array. The index of the next element to the pivot, that is, the left pointer, first_index + 1, marks the position where we begin to look for an element in the array that is greater than the pivot, as greater_than_pivot_index = first_index + 1. The right pointer less_than_pivot_index variable points to the position of the last element in the less_than_pivot_index = index_of_last_element list, where we begin the search for the element that is less than the pivot:

    while True: 

        while unsorted_array[greater_than_pivot_index] < pivot and 
              greater_than_pivot_index < last_index: 
              greater_than_pivot_index += 1 

        while unsorted_array[less_than_pivot_index] > pivot and 
              less_than_pivot_index >= first_index: 
              less_than_pivot_index -= 1 

At the beginning of the execution of the main while loop, the array looks like this:

The first inner while loop moves one index to the right until it lands on index 2, because the value at that index is greater than 43. At this point, the first while loop breaks and does not continue. At each test of the condition in the first while loop, greater_than_pivot_index += 1 is evaluated only if the while loop's test condition evaluates to True. This makes the search for an element, greater than the pivot, progress to the next element on the right.

The second inner while loop moves one index at a time to the left, until it lands on index 5, whose value, 20, is less than 43:

At this point, neither inner while loop can be executed any further:

    if greater_than_pivot_index < less_than_pivot_index: 
        temp = unsorted_array[greater_than_pivot_index] 
            unsorted_array[greater_than_pivot_index] =    
                unsorted_array[less_than_pivot_index] 
            unsorted_array[less_than_pivot_index] = temp 
    else: 
        break

Since greater_than_pivot_index < less_than_pivot_index, the body of the if statement swaps the element at those indexes. The else condition breaks the infinite loop any time that greater_than_pivot_index becomes greater than less_than_pivot_index. In such a condition, it means that greater_than_pivot_index and less_than_pivot_index have crossed over each other.

Our array now looks like the following:

The break statement is executed when less_than_pivot_index is equal to 3 and greater_than_pivot_index is equal to 4.

As soon as we exit the while loop, we interchange the element at unsorted_array[less_than_pivot_index] with that of less_than_pivot_index, which is returned as the index of the pivot:

    unsorted_array[pivot_index]=unsorted_array[less_than_pivot_index] 
    unsorted_array[less_than_pivot_index]=pivot 
    return less_than_pivot_index 

The following diagram shows how the code interchanges 4 with 43 as the last step in the partitioning process:

To recap, the first time the quick_sort function was called, it was partitioned about the element at index 0. After the return of the partitioning function, we obtain the array in the order of [4, 3, 20, 43, 89, 77].

As you can see, all elements to the right of element 43 are greater than 43, while those to the left are smaller. Thus, the partitioning is complete.

Using the split point 43 with index 3, we will recursively sort the two sub-arrays, [4, 30, 20] and [89, 77], using the same process we just went through.

The body of the main quick_sort function is as follows:

    def quick_sort(unsorted_array, first, last): 
        if last - first <= 0: 
            return 
    else: 
        partition_point = partition(unsorted_array, first, last) 
        quick_sort(unsorted_array, first, partition_point-1) 
        quick_sort(unsorted_array, partition_point+1, last) 

The quick_sort function is a very simple method, taking up no more than six lines of code. The heavy lifting is done by the partition function. When the partition method is called, it returns the partition point. This is the point in the unsorted_array array where all elements to the left are less than the pivot value, and all elements to its right are greater than it.

When we print the state of unsorted_array immediately after the partition progress, we see clearly how the partitioning happens:

Output:
[43, 3, 20, 89, 4, 77]
[4, 3, 20, 43, 89, 77]
[3, 4, 20, 43, 89, 77]
[3, 4, 20, 43, 77, 89]
[3, 4, 20, 43, 77, 89]

Taking a step back, let's sort the first sub-array after the first partition has happened. The partitioning of the [4, 3, 20] sub-array will stop when greater_than_pivot_index is at index 2, and less_than_pivot_index is at index 1. At that point, the two markers are said to have crossed. Because greater_than_pivot_index is greater than less_than_pivot_index, further execution of the while loop will cease. Pivot 4 will be exchanged with 3, while index 1 is returned as the partition point.

In the quicksort algorithm, the partition algorithm takes O(n) time. As the quicksort algorithm follows the divide and conquer paradigm, it takes O(log n) time; therefore, the overall average-case runtime complexity of the quicksort algorithm is O(n) * O(log n) = O(n log n). The quicksort algorithm gives a worst-case runtime complexity of O(n²). The worst-case complexity for the quicksort algorithm would be when it selects the worst pivot point every time, and one of the partitions always has a single element. For example, if the list is already sorted, the worst-case complexity would occur if the partition picks the smallest element as a pivot point. When worst-case complexity does occur, the quicksort algorithm can be improved by using the randomized quicksort. The quicksort algorithm is very efficient when sorting large amounts of data compared to the other aforementioned algorithms for sorting.