merge_sort.py

"""
Merge sort is a divide and conquer algorithm that divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.
"""


class Solution:
    def merge_sort(self, nums):
        n = len(nums)
        if n <= 1:
            return nums

        mid = n // 2
        left_half = self.merge_sort(nums[:mid])
        right_half = self.merge_sort(nums[mid:])

        return self._merge(left_half, right_half)

    def _merge(self, left, right):
        i, j = 0, 0
        result = []

        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1

        result.extend(left[i:])
        result.extend(right[j:])

        return result

        # Time Complexity: O(n log n)
        # Space Complexity: O(n)


if __name__ == "__main__":
    solution = Solution()

    nums = [38, 27, 43, 3, 9, 82, 10]
    result = solution.merge_sort(nums)
    assert result == [3, 9, 10, 27, 38, 43, 82]
    print(result)
    print("Test Case Passed!")