Sort an Array

SortingDivide and Conquer

MediumLeetCode #912

20 min

Problem Statement

Given an array of integers nums, sort the array in ascending order and return it.

You must solve the problem without using any built-in sorting functions.

Example

Example 1:

nums: [5, 2, 3, 1]

Output: [1, 2, 3, 5]

Solution

A standard and efficient way to solve this problem is by using the Merge Sort algorithm. It's a classic "Divide and Conquer" algorithm with a time complexity of O(n log n).

Merge Sort works by recursively splitting the array into halves until each subarray contains a single element. Then, it merges these subarrays back together in sorted order.

Algorithm Steps (Merge Sort)

Recursively divide the array into two halves until you reach subarrays of size 1.
Merge the smaller sorted subarrays back together.
Create two temporary arrays for the left and right halves.
Compare elements from the left and right halves and place the smaller element into the original array.
Continue until one of the halves is exhausted.
Copy any remaining elements from the non-exhausted half.

Merge Sort Visualization

Ready to sort.

Sort an Array (Merge Sort)


class Solution:
    def sortArray(self, nums: list[int]) -> list[int]:
        if len(nums) <= 1:
            return nums
        
        mid = len(nums) // 2
        left_half = self.sortArray(nums[:mid])
        right_half = self.sortArray(nums[mid:])
        
        return self.merge(left_half, right_half)

    def merge(self, left: list[int], right: list[int]) -> list[int]:
        merged = []
        i, j = 0, 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                j += 1
        
        merged.extend(left[i:])
        merged.extend(right[j:])
        return merged