Exploring the Time and Space Complexities of Quick Sort

Quick Sort is a divide-and-conquer sorting algorithm. It works by

1. Selecting a pivot element.
2. Partitioning the array into two sub-arrays (one with elements less than the pivot and one with elements greater than the pivot).
3. And then recursively sorting the sub-arrays.

def quick_sort(lst):
    length = len(lst)
    
    # Base case
    if length <= 1:
        return lst     
    else:
        # Choose the last element as the pivot
        pivot = lst.pop()

    # Partition step: Divide elements into 
    # left (<= pivot) and right (> pivot)
    right = []
    left = []

    for element in lst:       
        if element > pivot:
            right.append(element)        
        else:
            left.append(element)

    # Recursive step: Sort left and right partitions
    # Then combine with pivot
    return quick_sort(left) + [pivot] + quick_sort(right)

template<typename T>
int partition(vector<T>& arr, int low_index, int high_index) {
    // Consider the last element as pivot
    T pivot = arr[high_index];
 
    int i = low_index;
    int j = high_index-1;
 
    while(true) { 
        // Find element larger than pivot
        while(i < high_index && arr[i] < pivot) {
            ++i;
        }

        // Find element smaller than pivot
        while(j >= low_index && arr[j] > pivot) {
            --j;
        }

        // If two pointers crossover 
        if(i >= j) {
            break;
        }

        // If a smaller element exists after the larger element
        swap(arr[i], arr[j]);
    }
 
    // Position the pivot at its final position
    swap(arr[i], arr[high_index]);
 
    // Return the final index of the pivot
    return i;
}
 
template<typename T>
void quick_sort(vector<T>& arr, int low_index, int high_index) {
    // Return vector has less than two elements
    if(low_index >= high_index) {
        return;
    }

    // Partition the vector and get the final index of the pivot
    int pivot_index = partition(arr, low_index, high_index);
 
    // Recursively sort the left part
    quick_sort(arr, low_index, pivot_index-1);
 
    // Recursively sort the right part
    quick_sort(arr, pivot_index+1, high_index);
}

Time Complexity

Best Case Time Complexity: O(n logn)

In the best case, the pivot divides the array into two nearly equal halves at each recursive step.

Consider the following array:

[4, 2, 5, 3, 1]

Here, we choose the right-most element as pivot i.e. 1.

• Left sub-array: []
• Right sub-array: [4, 2, 5, 3]

In the second step, the pivot element is 3, which divides the array into almost equal halves ([2] and [4, 5]).

The new right sub-array is similarly divided into almost equal halves in each successive step.

In this scenario, each partitioning operation takes O(n) time, and the recursion depth is O(logn). Therefore, the total time complexity is O(n logn).

Worst Case Time Complexity: <katex>O(n^{2})</katex>

In the worst case, the pivot is always the smallest or largest element in multiple steps of recursion, which causes the array to be divided into uneven partitions. This results in a recursion depth of O(n).

Consider the reverse-sorted array:

[5, 4, 3, 2, 1]

Here, we choose the right-most element as pivot i.e. 1.

• Left sub-array: []
• Right sub-array: [5, 4, 3, 2]

In the second step, the pivot element is 2, which divides the array again into unequal halves. The array is similarly divided into unequal halves in each successive step.

In this scenario, each partitioning operation takes O(n) time, and the recursion depth is O(n). Therefore, the total time complexity is <katex>O(n^{2})</katex>.

Average Case Time Complexity: O(n logn)

In the average case, quick sort performs well with O(n logn) time complexity.

Assuming that the pivot divides the array into roughly equal parts, each partitioning step takes O(n) time, and the recursion depth is O(logn).

Space Complexity of Quick Sort: O(logn)

Quick sort is an in-place sorting algorithm. However, it uses additional space on the call stack due to recursion.

The space complexity is O(logn) for the average and best cases, where the recursion depth is proportional to the logarithm of the array size.

In the worst case (when the pivot always divides the array poorly), the space complexity can degrade to O(n).

However, such worst cases are extremely rare, so the space complexity is practically O(logn).

Summary: Time and Space Complexity

When to Use Quick Sort?

Quick sort is one of the most efficient and widely used sorting algorithms, especially for large datasets. Alongside insertion and merge sort, it's one of the most preferred sorting algorithms among programmers..

When to Use:

1. Large Datasets: Quick sort is fast for large datasets with an average-case time complexity of O(n logn).
2. In-Place Sorting: Quick sort doesn't require additional memory for sorting, making it suitable for environments with limited memory.
3. Randomly Ordered Data: Quick sort performs well with random data (as long as a good pivot is chosen).

When to Avoid:

1. Small Datasets: Algorithms like Insertion Sort might be more efficient here because of lower overhead.
2. Unbalanced Data: If the data is nearly sorted or reverse sorted, quick sort can degrade to <katex>O(n^{2})</katex>. In such cases, other algorithms like Merge Sort may perform better.

Here is a comparison of quick sort's performance in different scenarios:

Quick sort's performance is heavily dependent on the choice of pivot. With the right-most pivot, the worst case occurs more often with sorted or nearly sorted data.