Merge Sort

Introduction

Merge sort is another popular algorithm, with time complexity as O(nlogn). It’s leveraging the principle of divide and conquer, and this is definitely the algorithm we should master.

Algorithm

We recursively split the array into 2 parts, sort them seperately, and merge them back. The downside of this algorithm is we need to allocate extra space for merging the 2 sorted subarrays, and then copying them back to original array.

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if not nums:
            return nums
        self.merge_sort(nums, 0, len(nums) - 1, [None for _ in range(len(nums))])
        return nums
        
    def merge_sort(self, nums: List[int], start: int, end: int, temp: List[int]):
        if start >= end:
            return
        mid  = (start + end) // 2
        self.merge_sort(nums, start, mid, temp)
        self.merge_sort(nums, mid + 1, end, temp)
        self.merge(nums, start, end, temp)

    def merge(self, nums: List[int], start: int, end: int, temp: List[int]):
        mid = (start + end) // 2
        left_index, right_index = start, mid + 1
        temp_index = start
        while left_index <= mid and right_index <= end:
            if nums[left_index] < nums[right_index]:
                temp[temp_index] = nums[left_index]
                left_index += 1
            else:
                temp[temp_index] = nums[right_index]
                right_index += 1
            temp_index += 1
        
        while left_index <= mid:
            temp[temp_index] = nums[left_index]
            left_index += 1
            temp_index += 1
        
        while right_index <= end:
            temp[temp_index] = nums[right_index]
            right_index += 1
            temp_index += 1
        
        for i in range(start, end + 1):
            nums[i] = temp[i]

Conclusion

Merge sort is another classical algorithms used for sorting. Time complexity is O(nlogn). It’s easy to implement. However, it needs to use extra O(n)space.