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

         

Merge Sort

Algorithm:

• Iteratively Divide the list to two halves
• Sort and Merge the divided list until one list remains recursively

Time Complexity:

• Best/Worst/Average: O(nlogn) -list is divided into two halves and it takes linear time to merge the list back.

Space Complexity:

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

In-place: yes
Stable: yes

Python Implementation

def merge_sort(arr):
    m = len(arr)/2
    L = arr[:m]
    R = arr[m:]
    merge_sort(L)
    merge_sort(R)
    i = j = k = 0
   while i < len(L) and j < len(R):
       if L[i] < R[j]:
            arr[k] = L[i]
            i += 1
       else:
             arr[k] = R[j]
             j += 1
       k += 1
     
    while i < len(L):
           arr[k] = L[i]
           i += 1
           k += 1
    while j< len[R]:
           arr[k] = R[j]
           j += 1
           k += 1
         

Insertion Sort

In insertion sort, the sorting task is similar to that of sorting a deck of cards.

Algorithm:

1. Start at the beginning
2. Find the next element and bring it to its sorted position

 Time Complexity:

• Best: O(n) - when the list is already sorted
• Worst: O(n2) - when required to reverse the entire list

Space Complexity:

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

In-place: yes
Stable: yes

Python Implementation
def insertion_sort(arr):
    n = len(arr)
    for i in range(n):
        j = i
        while j > 0 and arr[j-1] > arr[j]:
            arr[j-1], arr[j] = arr[j], arr[j-1]
            j -= 1

Selection Sort

Algorithm:

• Find smallest element with linear scan
• Move it to the front
• Continue until all elements are in place

Time Complexity:

• Best: O(n2) - when the list is already sorted (https://stackoverflow.com/questions/43298396/best-case-time-complexity-for-selection-sort)
• Worst: O(n2) - when required to reverse the list

Space Complexity:

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

In-place: yes
Stable: yes

Python Implementation:
def selection_sort(arr):
    n = len(arr)
    for i range(n):
        min_index = i
        for j in range(i+1, n):
            if a[min_index] > a[j]:
                 min_index = j
    a[i], a[min_index] = a[min_index], a[i]

Bubble Sort

Algorithm:

• Start at the beginning
• Swap first two element if first is greater than second
• Continue to next pair
• Repeat until sorted

Time Complexity:

• Best: O(n) - when the list is already sorted
• Worst: O(n2) - when required to reverse the list

Space Complexity:

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

In-place: yes
Stable: yes

Python Implementation

def bubble_sort(array):
    n = len(array)
    for j in range(n):
        for i in range(n-1-j):
            if a[i] > a[i+1]:
                a[i+1], a[i] = a[i], a[i+1]

Stable Sorting Algorithms

A sorting algorithm is called stable sorting algorithms if the order of the original values with same precedence is retained over in the final output.

e.g. a list of names [alex, bob, alice, judy, tom] has the output [alex, alice ,bob, judy, tom]. Here the precedence of alex over alice is retained in the output.

Sorting Algorithm that are stable:

• Bubble Sort
• Insertion Sort
• Merge Sort

Not stable sorting algorithms:

• Heap Sort
• Quick Sort

In Place Algorithm

In place algorithms:

• focus on space efficiency
• uses no auxiliary data structures and uses very small extra space
• have O(1) space complexity (strict definition) to O(log n) space complexity (broad definition)

Side Effects:

• usually overwrites the original data to create the modified output
• may need more time in some cases

Examples:
Reversing a sorted list in-place.
a = [1,2,3,4,5]
n = len(a)
temp = 0
for i in range(n/2):
     temp = a[n-1-i]
    a[n-1-i] = a[i]
    a[i] = temp

In-place sorting algorithms:

• Bubble Sort
• Selection Sort