Quick Sort

Algorithm:

• Select a pivot element in the array
• Move the selected pivot to its correct location in array such that all elements on its left is less than it and all elements on the right are greater than it.

Time Complexity:

• Best/Average: O(nlogn) -list is divided into two halves and it takes linear time to merge the list back.
• Worst: O(n2)- when either largest or smallest element is selected as pivot. Also, when the list is already sorted.

Space Complexity:

• O(1) - usually no extra space is required

In-place: yes
Stable:no

Python Implementation

arr = [1,2,5,4,9]
low = 0
high = len(arr)-1

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr,low,pi-1)
        quick_sort(arr,pi+1,high)
    return arr

def partition(arr, low, high):
    pivot = arr[high]
    i = low -1
    for j in range(low, high-1):
        if arr[j] < pivot:
            i += 1
            arr[j], arr[i] = arr[i], arr[j]
   arr[i+1], arr[high] = arr[high], arr[i+1]
   return i+1