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