Sorting Algorithms in Python

Sorting is a key concept in computer science and algorithm design. It helps organize data efficiently and is frequently asked in coding interviews. In this post, we cover four commonly taught sorting algorithms: Bubble Sort, Selection Sort, Insertion Sort, and Merge Sort. Each is illustrated with a simple problem, Python implementation, and analysis of time and space complexity.

1. Bubble Sort
Problem
Given an integer array nums, sort it in ascending order using Bubble Sort.

class Solution:
def bubbleSort(self, nums):
n = len(nums)
for i in range(n):
for j in range(0, n-i-1):
if nums[j] > nums[j+1]:
nums[j], nums[j+1] = nums[j+1], nums[j]
return nums

# Example usage
nums = [5, 2, 3, 1]
sol = Solution()
print("Sorted array:", sol.bubbleSort(nums))

Time Complexity:
Best Case: O(n)
Worst Case: O(n²)
Average Case: O(n²)
Space Complexity: O(1)

2. Selection Sort
Problem
Given an array of integers, sort it in ascending order using Selection Sort.

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

arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("Sorted array:", arr)

Time Complexity:
Best Case: O(n²)
Worst Case: O(n²)
Average Case: O(n²)
Space Complexity: O(1)

3. Insertion Sort
Problem
Given an array of numbers, sort them in ascending order using Insertion Sort.

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

arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print("Sorted array:", arr)

Time Complexity:
Best Case: O(n)
Worst Case: O(n²)
Average Case: O(n²)
Space Complexity: O(1)

4. Merge Sort

Problem
Given an array of integers, sort it using the divide-and-conquer approach (Merge Sort).

def merge_sort(arr):
if len(arr) > 1:
mid = len(arr)//2
L = arr[:mid]
R = arr[mid:]

    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

arr = [38, 27, 43, 3, 9, 82, 10]
merge_sort(arr)
print("Sorted array:", arr)

Time Complexity:
Best Case: O(n log n)
Worst Case: O(n log n)
Average Case: O(n log n)
Space Complexity: O(n)