Firstly, See About page.

Just focus on the problem Sort an Array where candidates to implement sorting from scratch, with \(O(n\log n)\) time complexity

\(O(n^2)\) Sorting

Selection Sort

Traverse the array, repetitively swap a position’s value with the smallest element from it to the end. This algorithm performs unstable sorting, as the relative order of equal elements are not preserved. No practical application.

Complexity

Time complexity: \(O(n^2)\) - \(\Omega(n)\)
Memory complexity: \(O(1)\)

Code

class Solution:
    def sortArray(self, nums: List[int], sort_type: str = 'selection') -> List[int]:
        if sort_type = 'selection':
            self.selection_sort(nums)
        return nums

    def selection_sort(self, nums: List[int]) -> None:
        for i in range(len(nums)):
            min_index = i
            
            for j in range(i + 1, len(nums)):
                if nums[j] < nums[min_index]:
                    min_index = j
            
            nums[i], nums[min_index] = nums[min_index], nums[i]

Bubble Sort

Traverse the array, repetitively swap two positions at a time if needed. A stable sorting algorithm, but still no practical application.

Complexity

Time complexity: \(O(n^2)\) - \(\Omega(n)\)
Memory complexity: \(O(1)\)

Code

class Solution:
    def sortArray(self, nums: List[int], sort_type: str = 'selection') -> List[int]:
        if sort_type = 'selection':
            self.selection_sort(nums)
        if sort_type = 'bubble':
            self.bubble_sort(nums)
        return nums

    def selection_sort(self, nums: List[int]) -> None:
        for i in range(len(nums)):
            min_index = i
            
            for j in range(i + 1, len(nums)):
                if nums[j] < nums[min_index]:
                    min_index = j
            
            nums[i], nums[min_index] = nums[min_index], nums[i]
    
    def bubble_sort(self, nums: List[int]) -> None:
        has_swapped = True

        while has_swapped:
            has_swapped = False
            for i in range(len(nums) - 1):
                if nums[i] > nums[i + 1]:
                    nums[i], nums[i + 1] = nums[i + 1], nums[i]
                    has_swapped = True

Insertion Sort

Sort the array from left to right. At each element, find its right position in the next sorted array by comparison with the previous element and move it down to the right place one step at a time. Insertion sort has practical applications as it offers good performance on small arrays (<15 elements) or nearly-sorted arrays.

Complexity

Time complexity: \(O(n^2)\)
Memory complexity: \(O(1)\)

Code

class Solution:
    def sortArray(self, nums: List[int], sort_type: str = 'selection') -> List[int]:
        if sort_type = 'selection':
            self.selection_sort(nums)
        if sort_type = 'bubble':
            self.bubble_sort(nums)
        if sort_type = 'insertion':
            self.insertion_sort(nums)
        return nums

    def selection_sort(self, nums: List[int]) -> None:
        for i in range(len(nums)):
            min_index = i
            
            for j in range(i + 1, len(nums)):
                if nums[j] < nums[min_index]:
                    min_index = j
            
            nums[i], nums[min_index] = nums[min_index], nums[i]
    
    def bubble_sort(self, nums: List[int]) -> None:
        has_swapped = True

        while has_swapped:
            has_swapped = False
            for i in range(len(nums) - 1):
                if nums[i] > nums[i + 1]:
                    nums[i], nums[i + 1] = nums[i + 1], nums[i]
                    has_swapped = True
    
    def insertion_sort(self, nums: List[int]) -> None:
        for i in range(1, len(nums)):
            current_index = i

            while current_index > 0 and nums[current_index - 1] > nums[current_index]:
                # Swap elements that are out of order
                nums[current_index], nums[current_index - 1] = nums[current_index - 1], nums[current_index]
                current_index -= 1

\(O(n \log n)\) Sorting

Merge Sort

Many resources will call this approach Divide and Conquer. The idea (by John von Neumann no less) was dividing the the array into half recursively, sort each half, and then merge the halves together to form the final array.

Complexity

Time complexity: \(O(n \log n)\)
Memory complexity: \(O(n)\) - an \(O(\log n)\) recursive call stack and an \(O(n)\) final array

Code

from typing import List

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        self._mergeSort(nums)
        return nums
    
    def _mergeSort(self, nums: List[int]) -> None:
        if len(nums) > 1:
            mid = len(nums) // 2
            left_half = nums[:mid]
            right_half = nums[mid:]

            self._mergeSort(left_half)
            self._mergeSort(right_half)

            self._merge(nums, left_half, right_half)
    
    def _merge(self, nums: List[int], left_half: List[int], right_half: List[int]) -> None:
        left_pointer = right_pointer = num_pointer = 0

        while left_pointer < len(left_half) and right_pointer < len(right_half):
            if left_half[left_pointer] < right_half[right_pointer]:
                nums[num_pointer] = left_half[left_pointer]
                left_pointer += 1
            else:
                nums[num_pointer] = right_half[right_pointer]
                right_pointer += 1
            num_pointer += 1
        
        if left_pointer < len(left_half):
            nums[num_pointer:] = left_half[left_pointer:]
        elif right_pointer < len(right_half):
            nums[num_pointer:] = right_half[right_pointer:]

Quicksort

A randomized sorting algorithm that on average matches the performance of Merge Sort.

Heap Sort

Sort with a heap. Requires implementation of a heap to sort the array with its tree and then construct back the array. Performance similar to Merge Sort, with a better memory complexity as the value is modified in place.

Code

# Bad practice - these closures turn things crazy to debug.

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        # Function to heapify a subtree (in top-down order) rooted at index i.
        def heapify(n: int, i: int):
            # Initialize largest as root 'i'.
            largest = i
            left = 2 * i + 1
            right = 2 * i + 2
            # If left child is larger than root.
            if left < n and nums[left] > nums[largest]:
                largest = left
            # If right child is larger than largest so far.
            if right < n and nums[right] > nums[largest]:
                largest = right
            # If largest is not root swap root with largest element
            # Recursively heapify the affected sub-tree (i.e. move down).
            if largest != i:
                nums[i], nums[largest] =  nums[largest], nums[i]
                heapify(n, largest)

        def heap_sort():
            n = len(nums)
            # Build heap; heapify (top-down) all elements except leaf nodes.
            for i in range(n // 2 - 1, -1, -1):
                heapify(n, i)
            # Traverse elements one by one, to move current root to end, and
            for i in range(n - 1, -1, -1):
                nums[0], nums[i] = nums[i], nums[0]
                # call max heapify on the reduced heap.
                heapify(i, 0)

        heap_sort()
        return nums

Sorting

\(O(n^2)\) Sorting

Selection Sort

Complexity

Code

Bubble Sort

Complexity

Code

Insertion Sort

Complexity

Code

\(O(n \log n)\) Sorting

Merge Sort

Complexity

Code

Quicksort

Heap Sort

Code

Range-dependent Sorting

Bucket Sort

Counting Sort

Radix Sort