Insertion Sort

Analysis: Maintains a sorted subarray, inserting one element at a time into this subarray while preserving order until completion. This is an in-place sorting algorithm requiring no additional memory space. Time complexity varies based on input randomness - better performance with higher randomness, worse performance with nearly reverse-sorted data.

def insertion_sort(array):
    size = len(array)
    position = 1
    while position < size:
        current_value, index = array[position], position
        while index > 0 and array[index - 1] > current_value:
            array[index] = array[index - 1]
            index -= 1
        array[index] = current_value
        position += 1

Selection Sort

Analysis: In an array of n elements, find the maximum value among the first n items and swap it with the nth position, then find the maximum among the first n-1 items and swap with the (n-1)th position, continuing until completion. Time complexity shows inferior performance compared to insertion sort with highly randomized data, but performs notably better than insertion sort with nearly reverse-sorted arrays.

def selection_sort(array):
    size = len(array)
    counter = 0
    while counter < size:
        max_pos, iterator = 0, 0
        while iterator < size - counter:
            if array[max_pos] < array[iterator]:
                max_pos = iterator
            iterator += 1
        array[size - 1 - counter], array[max_pos] = array[max_pos], array[size - counter - 1]
        counter += 1

Bubble Sort

Analysis: Starting from the first element, if an element is larger than its successor, swap them, then proceed to compare the next pair until completion. Time complexity can be optimized by setting a swap flag during each pass - if no swaps occur during a complete pass, sorting is complete. Therefore, if data is already nearly ordered, bubble sort may complete in shorter time, but in most cases, its efficiency is inferior to other sorting algorithms.

def bubble_sort(array):
    size = len(array)
    start = 0
    while start < size:
        end = size - 1
        has_swapped = False
        while end > start:
            if array[end] < array[end - 1]:
                array[end], array[end - 1] = array[end - 1], array[end]
                has_swapped = True
            end -= 1
        if not has_swapped:
            break
        start += 1

Shell Sort

Shell sort can be viewed as an improvement over insertion sort. While insertion sort compares adjacent elements, shell sort uses a gap sequence that decreases until reaching 1. In shell sort, insertion operations compare elements at intervals of x (where x belongs to the gap sequence). Shell sort performs better than both insertion and selection sorts, with time complexity approximately O(n^1.3).

def shell_sort(array):
    size = len(array)
    interval = size // 2
    while interval > 0:
        index = interval
        while index < size:
            temp_val, pos = array[index], index
            while pos >= interval and array[pos - interval] > temp_val:
                array[pos] = array[pos - interval]
                pos -= interval
            array[pos] = temp_val
            index += interval
        interval //= 2

The gap sequence used here is [size//2, size//4, ..., 1].

Quick Sort

Quick sort embodies the divide-and-conquer approach. First, select a pivot element from the array, place smaller elements to the left of the pivot and larger elements to the right, then recursively apply quick sort to the left and right subarrays until completion. Quick sort's efficiency depends on pivot selection - if the median is consistently chosen, performance is excellent, but if always choosing maximum or minimum values, performance degrades. Quick sort outperforms shell sort with average time complexity of O(n log n). This implementation always selects the first array element as pivot, performing well with highly randomized data but poorly with reverse-sorted data (potentially causing stack overflow).

def quick_sort(array):
    def partition(arr, low_idx, high_idx):
        pivot_element = arr[low_idx]
        while low_idx < high_idx:
            while low_idx < high_idx and arr[high_idx] >= pivot_element:
                high_idx -= 1
            arr[low_idx], arr[high_idx] = arr[high_idx], arr[low_idx]
            while low_idx < high_idx and arr[low_idx] <= pivot_element:
                low_idx += 1
            arr[low_idx], arr[high_idx] = arr[high_idx], arr[low_idx]
        return low_idx

    def _recursive_quick_sort(arr, low_idx, high_idx):
        if low_idx < high_idx:
            pivot_location = partition(arr, low_idx, high_idx)
            _recursive_quick_sort(arr, low_idx, pivot_location - 1)
            _recursive_quick_sort(arr, pivot_location + 1, high_idx)

    _recursive_quick_sort(array, 0, len(array) - 1)

To prevent stack overflow, set the maximum recursion limit:

import sys
sys.setrecursionlimit(3000)

Merge Sort

Merge sort achieves efficiency comparable to quick sort. While quick sort partitions arrays by element values, merge sort partitions by indices, always splitting arrays in half and merging sorted halves. For each partition, recursively call merge sort. Merge sort maintains stable performance with good results for both highly randomized and reverse-sorted data, with time complexity O(n log n).

def merge_sort(array):
    def _combine(left_arr, right_arr):
        i, j, result = 0, 0, []
        while i < len(left_arr) and j < len(right_arr):
            if left_arr[i] < right_arr[j]:
                result.append(left_arr[i])
                i += 1
            else:
                result.append(right_arr[j])
                j += 1
        result.extend(left_arr[i:])
        result.extend(right_arr[j:])
        return result
    
    if len(array) <= 1:
        return array
    
    mid_point = len(array) // 2
    left_half = merge_sort(array[:mid_point])
    right_half = merge_sort(array[mid_point:])
    
    return _combine(left_half, right_half)

Heap Sort

Heap sort utilizes heap data structure. Since Python's standard library heapq includes heap sort algorithms, the implementation can be concise. Heap sort maintains a binary heap (either min or max heap), repeatedly extracting the smallest element. Heap sort remains stable with good performance in both high randomness and reverse-sorted scenarios, with time complexity O(n log n).

Import the module first:

from heapq import *

def python_heap_sort(array):
    heapify(array)
    return [heappop(array) for i in range(len(array))]

A binary heap is a complete binary tree where root elements are always smaller than child elements (min heap). Building heap from array takes linear time complexity, while extracting elements takes logarithmic time. Complete binary trees can be stored using arrays.

class BinaryHeap:
    def __init__(self):
        self.storage = [0]
        self.count = 0

    def bubble_up(self, idx):
        while idx // 2 > 0:
            if self.storage[idx] < self.storage[idx // 2]:
                self.storage[idx], self.storage[idx // 2] = self.storage[idx // 2], self.storage[idx]
            idx //= 2

    def find_min_child(self, idx):
        if idx * 2 > self.count:
            return None
        elif idx * 2 + 1 > self.count:
            return idx * 2
        else:
            if self.storage[idx * 2] <= self.storage[idx * 2 + 1]:
                return idx * 2
            else:
                return idx * 2 + 1

    def bubble_down(self, idx):
        while True:
            min_child = self.find_min_child(idx)
            if not min_child:
                break
            if self.storage[idx] > self.storage[min_child]:
                self.storage[idx], self.storage[min_child] = self.storage[min_child], self.storage[idx]
            idx = min_child

    def add(self, value):
        self.storage.append(value)
        self.count += 1
        self.bubble_up(self.count)

    def extract(self):
        if self.count == 0:
            raise IndexError('The heap is empty')
        item = self.storage[1]
        self.remove(item)
        return item

    def remove(self, value):
        pos = self.storage.index(value)
        self.storage[pos] = self.storage[self.count]
        self.storage.pop()
        self.count -= 1
        self.bubble_down(pos)

    def build_heap(self, arr):
        self.storage = [0] + arr[:]
        self.count = len(arr)
        index = self.count // 2
        while index > 0:
            self.bubble_down(index)
            index -= 1

    def display(self):
        print(self.storage[1:])

    def __bool__(self):
        return bool(self.count)

def custom_heap_sort(array):
    heap_obj, output = BinaryHeap(), []
    heap_obj.build_heap(array)
    while heap_obj:
        output.append(heap_obj.extract())
    return output

These are common sorting algorithms. Let's test their performance.

import random
from time import time

num_elements = 20000
test_list = [random.random() for i in range(num_elements)]
random.shuffle(test_list)

functions = [list.sort, python_heap_sort, quick_sort, merge_sort, custom_heap_sort, shell_sort, insertion_sort, selection_sort, bubble_sort]

for function in functions:
    start_time = time()
    function(test_list.copy())
    end_time = time()
    print(f"{function.__name__}: {end_time - start_time}")

With high rnadomness, results show:

python_heap_sort: 0.01575779914855957
quick_sort: 0.024766206741333008
merge_sort: 0.02457451820373535
custom_heap_sort: 0.06661224365234375
shell_sort: 6.078854084014893
insertion_sort: 14.36155891418457
selection_sort: 33.40423130989075
bubble_sort: 48.74769401550293

With reverse-sorted data:

num_elements = 20000
test_list = [random.random() for i in range(num_elements)]
test_list.sort(reverse=True)

functions = [list.sort, python_heap_sort, quick_sort, merge_sort, custom_heap_sort, shell_sort, insertion_sort, selection_sort, bubble_sort]

for function in functions:
    start_time = time()
    function(test_list.copy())
    end_time = time()
    print(f"{function.__name__}: {end_time - start_time}")

python_heap_sort: 0.003007173538208008
quick_sort: 5.107363939285278
merge_sort: 0.014906883239746094
custom_heap_sort: 0.05798840522766113
shell_sort: 9.991580724716187
insertion_sort: 17.121063709259033
selection_sort: 12.812097787857056
bubble_sort: 25.45111322402954