Merge Sort In sorting n objects, merge sort has an average and worst-case performance of O(n log n).
Merge sort is a stable sort in the most implementations. The most common implementation does not sort in place, meaning it requires extra space.
Implementation in Python from typing import List # Python merge sort implementation # Time complexity: O(NlogN), space complexity: O(N) def merge_sort(nums: List[int]): # Base case if len(nums) <= 1: return nums mid = len(nums) // 2 left, right = merge_sort(nums[:mid]), merge_sort(nums[mid:]) return merge(left, right) def merge(left: List[int], right: List[int]): i, j = 0, 0 res = [] # Compare the elements in the left and right list and append the smaller one to the result list while i < len(left) and j < len(right): if left[i] <= right[j]: res.
Quick Sort In sorting n objects, quick sort has an average performance of O(n log n) and a worst performance of O(n^2).
Most implementations of quick sort are not stable, but sort in place, meaning it does not require extra space.
Implementation in Python # O(NLogN), space complexity O(n) in this case def quick_sort(nums): if len(nums) <= 1: return nums pivot = nums[len(nums) // 2] left = [n for n in nums if n < pivot] mid = [n for n in nums if n == pivot] right = [n for n in nums if n > pivot] return quick_sort(left) + mid + quick_sort(right) # Test cases if __name__ == "__main__": # Test case 1: Sorting an empty list arr1 = [] result1 = quick_sort(arr1) assert result1 == [], "Test case 1 failed" # Test case 2: Sorting a list with one element arr2 = [5] result2 = quick_sort(arr2) assert result2 == [5], "Test case 2 failed" # Test case 3: Sorting a list with multiple elements arr3 = [3, 6, 1, 8, 2, 4, 5, 7] result3 = quick_sort(arr3) assert result3 == [1, 2, 3, 4, 5, 6, 7, 8], "Test case 3 failed" # Test case 4: Sorting a list with duplicate elements arr4 = [3, 6, 1, 8, 2, 4, 5, 7, 1, 2] result4 = quick_sort(arr4) assert result4 == [1, 1, 2, 2, 3, 4, 5, 6, 7, 8], "Test case 4 failed" # Test case 5: Sorting a list with duplicate pivot elements arr5 = [3, 6, 1, 5, 4, 4, 5, 7, 1, 2] result5= quick_sort(arr5) assert result5 == [1, 1, 2, 3, 4, 4, 5, 5, 6, 7], "Test case 5 failed {0}".