Here are implementations of a few array sorting algorithms.

a = list('sortingexample')


### 1. Selection Sort

• Iteratively put the ith smallest element at ith location from the left.
• We maintain a sorted section from the left.
• In each iteration, we expand the sorted section by swap the smallest element from the unsorted section into the location.
def selection_sort(a):
n = len(a)
for i in range(n):
s = i
for j in range(i + 1, n):
if a[j] < a[s]:
s = j
a[i], a[s] = a[s], a[i]


### 2. Bubble Sort

• Iteratively put the ith largest element to ith location from the end.
• We maintain a sorted seciton from the right.
• In each iteration, we compare adjacent pairs of elements and swap larger values to the right until we reach the sorted part.
• Bubble sort can have O(N) best case time complexity, with a bit more code to detect if the array is sorted and terminates early.
def bubble_sort(a):
n = len(a)
for i in range(1, n):
swapped = False
for j in range(n - i):
if a[j] > a[j + 1]:
a[j + 1], a[j] = a[j], a[j + 1]
swapped = True
if not swapped: break


### 3. Insertion Sort

• Iteratively insert new element into the sorted part.
• We maintain a sorted section from the left.
• In each iteration, we sink one new element from the right to the correct location in the sorted part.
def insertion_sort(a):
n = len(a)
for i in range(n):
for j in range(i, 0, -1):
if a[j] < a[j - 1]:
a[j - 1], a[j] = a[j], a[j - 1]


### 4. Merge Sort

• Recursively divide the array into two halves, sort both(recursively) and then merge the two sorted array.
• It follows the Divide-and-Conquer paradigm.
# A quick and dirty non-inplace version
def merge_sort(a):
def merge(left, right):
merged = []
while left and right:
merged.append(left.pop() if left[-1] > right[-1] else right.pop())
merged.extend(left + right)
return merged[::-1]

if len(a) <= 1: return a
mid = len(a) // 2
left = merge_sort(a[:mid])
right = merge_sort(a[mid:])
return merge(left, right)

# A in place version
def merge_sort(a):
temp = a.copy()

def merge(low, mid, high):
for i in range(low, high + 1):
temp[i] = a[i]

i, j = low, mid + 1
for k in range(low, high + 1):
if i > mid:
a[k] = temp[j]
j += 1
elif j > high:
a[k] = temp[i]
i += 1
elif temp[j] < temp[i]:
a[k] = temp[j]
j += 1
else:
a[k] = temp[i]
i += 1

# bottom-up version
# n = len(a)
# step_size = 1
# while step_size < n:
#     for low in range(0, n, 2 * step_size):
#         mid = low + step_size - 1
#         high = min(n - 1, low + 2 * step_size - 1)
#         merge(low, mid, high)
#     step_size *= 2

# # top-down version
def _merge_sort(low, high):
if low >= high: return
mid = (low + high) // 2
_merge_sort(low, mid)
_merge_sort(mid + 1, high)
merge(low, mid, high)

_merge_sort(0, len(a) - 1)


### 5. Quick Sort

• Pick a random pivot item, put it in the right place by moving items smaller than it to its left and items larger than it to its right.
• Use the pivot item(since its in the right location now), to cut the problem in two halves and recursively sort the whole thing.
import random

# an inplace implementation, with random pivot item instead of shuffle and alwasy pick leftmost as pivot.
def quick_sort(a):
def partition(l, h):
if l >= h: return
p = random.randint(l, h)
a[l], a[p] = a[p], a[l]
pivot = a[l]
i, j = l, h
while i < j:
while i < h and a[i] <= pivot: i += 1
while j > l and a[j] >= pivot: j -= 1
if j > i and a[i] > a[j]: a[i], a[j] = a[j], a[i]
a[j], a[l] = a[l], a[j]
return j

def sort(l, h):
if h > l:
j = partition(l, h)
sort(l, j - 1)
sort(j + 1, h)

sort(0, len(a) - 1)


### 6. Heap Sort

• Heapify the array then poping item one at a time.
• See Heap section for how heap works.