Divide and Conquer

A Divide and Conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved. The solutions to the sub-problems are then combined to give a solution to the original problem [1].

Merge Sort

The Merge Sort is a classic Divide and Conquer algorithm [2]. This algorithm can be divided into two steps [2]:

  1. Divide the input list into n sub-lists, each containing one element.
  2. Repeatedly merge these sub-lists to produce new sorted sub-lists. This merge process is repeated until there is only one sub-list remaining.
from typing import List


class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        return self.merge_sort(nums)

    def merge_sort(self, nums: List[int]) -> List[int]:
        """
        Step 1) described above
        """
        if len(nums) <= 1:
            return nums

        mid = len(nums) // 2
        left = self.merge_sort(nums[:mid])
        right = self.merge_sort(nums[mid:])

        return self.merge(left, right)

    def merge(self, a: List[int], b: List[int]) -> List[int]:
        """
        Step 2) described above
        """
        res = []
        n, m = len(a), len(b)
        i = j = 0

        while i < n and j < m:
            if a[i] < b[j]:
                res.append(a[i])
                i += 1
            else:
                res.append(b[j])
                j += 1

        # add remained elements from `a` (if any)
        res.extend(a[i:])
        # add remained elements from `b` (if any)
        res.extend(b[j:])

        return res

The solution can be verified here.

References