0912. Sort an Array

Medium | Array + Sort | 276 ms (91.37%), 21.7 MB (50.89% )

❓ Problem Statement

Source: LeetCode - Sort an Array GitHub: Solution / Performance

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

✍🏻 Constraints & Example

Constraints:

• 1 <= nums.length <= 5 * 10^4

• -5 * 10^4 <= nums[i] <= 5 * 10^4

Input: nums = [5,2,3,1]
Output: [1,2,3,5]

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

💡 Ideas

There are numerous ways to sort an array or a linked list. I prefer to take merge sort for sorting an array or linked list, while quick sort can be implemented concisely.

Reference: LeetCode Discussion - Python, Python3, Java

❶ Merge Sort

Recursively divide the input array into two halves, then merge them.

1. For dividing the array, it is straightforward in Python by array[:length // 2]

2. For merging and sorting two arrays, excepting iterating through each element in two arrays, need to take care of the remaining elements due to unequal length of arrays.

Note that we don't need to do division when the input array has only one element.

# Example:
#   array = [3, 4, 5, 2, 1]
#   n = 5

[3, 4, 5, 2, 1]  --'divide'-->  [3, 4], [5, 2, 1]

# Part 1
# -------------------------------------------------
[3, 4]      --'divide'--> [3], [4]
[3], [4]    --'merge'---> [3, 4]

# Part 2
# -------------------------------------------------
[5, 2, 1]   --'divide'--> [5], [2, 1]

# Part 2'
# -------------------------------------------------
[2, 1]      --'divide'--> [2], [1]
[2], [1]    --'merge'---> [1, 2]

# Merge Part 2 and Part 2'
# -------------------------------------------------
[5], [1, 2] --'merge'---> [1, 2] + [5] = [1, 2, 5]

# Merge Part 1 and Part 2
# -------------------------------------------------
[3, 4], [1, 2, 5] --'merge'--> [1, 2, 3, 4] + [5] = [1, 2, 3, 4, 5]

❷ Quick Sort

Recursively do partition operation in each Sorting iteration.

1. For sorting function, it serves as a wrapper to do partition and take care of the termination of recursion by rIndex == lIndex or rIndex - lIndex == 1

2. For partitioning operation, we randomly pick a pivot by the index. Then, we move elements with smaller values to its left side and move elements with larger values to its right side by two pointers. Finally, return pivot's index.

# Example:
#   array = [3, 4, 5, 2, 1]
#   n = 5
#   quickSort(array, lIndex=0, rIndex=n=5)

# Part 1: partition(array, lIndex=0, rIndex-1=4)
[3, 4, '5', 2, 1]  -->  pivot = array[(lIndex + rIndex) // 2] = 5

# Step 1: Move pivot to the end by pivot=rIndex=4
[3, 4, '5', 2, 1]  -->  [3, 4, 1, 2, '5']
# Step 2: Using two pointers to move smaller elements to left
[3, 4, 1, 2, '5']  -->  [3, 4, 1, 2, '5']  # place-pointer = 4
# Step 3: Move back the Pivot by swapping place-pointer and rIndex
[3, 4, 1, 2, '5']  -->  [3, 4, 1, 2, '5']
# Step 4: Return place-pointer's index = 4

# Part 2: Sort
sort(array, lIndex=0, rIndex=pivot=4)
sort(array, lIndex=pivot + 1, rIndex=5) # lIndex == rIndex, done

# ------------------------------------------

# Part 1: partition(array, lIndex=0, rIndex-1=3)
[3, '4', 1, 2, 5]  -->  pivot = array[(lIndex + rIndex) // 2] = 4

# Step 1: Move pivot to the end by pivot=rIndex=3
[3, '4', 1, 2, 5]  -->  [3, 2, 1, '4', 5]
# Step 2: Using two pointers to move smaller elements to left
[3, 2, 1, '4', 5]  -->  [3, 2, 1, '4', 5]  # place-pointer = 3
# Step 3: Move back the Pivot by swapping place-pointer and rIndex
[3, 2, 1, '4', 5]  -->  [3, 2, 1, '4', 5]
# Step 4: Return place-pointer's index = 3

# Part 2: Sort
sort(array, lIndex=0, rIndex=pivot=3)
sort(array, lIndex=pivot + 1, rIndex=4) # lIndex == rIndex, done

# ------------------------------------------

# Part 1: partition(array, lIndex=0, rIndex-1=2)
[3, '2', 1, 4, 5]  -->  pivot = array[(lIndex + rIndex) // 2] = 2

# Step 1: Move pivot to the end by pivot=rIndex=2
[3, '2', 1, 2, 5]  -->  [3, 1, '2', 4, 5]
# Step 2: Using two pointers to move smaller elements to left
[3, 1, '2', 4, 5]  -->  [1, 3, '2', 4, 5]  # place-pointer = 1
# Step 3: Move back the Pivot by swapping place-pointer and rIndex
[1, 3, '2', 4, 5]  -->  [1, '2', 3, 4, 5]
# Step 4: Return place-pointer's index = 1

# Part 2: Sort
sort(array, lIndex=0, rIndex=pivot=1)   # rIndex - lIndex = 1, done
sort(array, lIndex=pivot + 1, rIndex=2) # lIndex == rIndex, done

🤖 Python3

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        # return self.quickSort(nums)
        # return self.quickSort1(nums)
        return self.mergeSort(nums)
        
    def mergeSort(self, nums: List[int]) -> List[int]:
        # ==================================================
        #  Array + Merge Sort                              =
        # ==================================================
        # time  : O(nlogn)
        # space : O(n)
        
        def merge(left: List[int], right: List[int]) -> List[int]:
            ret, p1, p2 = [], 0, 0
            while p1 < len(left) and p2 < len(right):
                if left[p1] <= right[p2]:
                    ret += [left[p1]]
                    p1 += 1
                else:
                    ret += [right[p2]]
                    p2 += 1
            ret += left[p1:] or right[p2:]
            return ret
        
        if len(nums) == 1: return nums
        
        left, right = self.mergeSort(nums[:len(nums)//2]), self.mergeSort(nums[len(nums)//2:])
        return merge(left, right)
    
    def quickSort(self, nums: List[int]) -> List[int]:
        # ==================================================
        #  Array + Quick Sort                              =
        # ==================================================
        # time  : O(nlogn)
        # space : O(logn)
        
        def sort(nums: List[int], left: int, right: int) -> None:
            if right == left or right - left == 1: return
            
            pivot = partition(nums, left, right - 1)
            sort(nums, left, pivot)
            sort(nums, pivot + 1, right)
            
        def partition(nums: List[int], left: int, right: int) -> int:
            randomNum = (left + right) // 2
            pivot = right
            nums[randomNum], nums[pivot] = nums[pivot], nums[randomNum]
            placeP = left
            for i in range(left, right):
                if nums[i] < nums[pivot]:
                    nums[placeP], nums[i] = nums[i], nums[placeP]
                    placeP += 1
            nums[pivot], nums[placeP] = nums[placeP], nums[pivot]
            return placeP
        
        sort(nums, 0, len(nums))
        return nums
    
    def quickSort1(self, nums: List[int]) -> List[int]:
        #  (base case)
        if not nums or len(nums) == 1: return nums
        
        # ==================================================
        #  Array + Quick Sort                              =
        # ==================================================
        # time  : O(nlogn)
        # space : O(logn)
        
        pivot = nums[len(nums) // 2]
        lt, eq, lg = list(), list(), list()
        for num in nums:
            if num == pivot: eq += [num]
            elif num > pivot: lg += [num]
            else: lt += [num]
                
        return self.quickSort(lt) + eq + self.quickSort(lg)

🤖 Java

class Solution {
    public int[] sortArray(int[] nums) {
        return quickSort(nums);
        // return mergeSort(nums);
    }
    
    /**  
     * @time  : O(nlog(n))
     * @space : O(n)
     */
    public int[] mergeSort(int[] nums) {
        sortMerge(nums, 0, nums.length - 1);
        return nums;
    }
    
    private void sortMerge(int[] nums, int left, int right) {
        if(left < right) {
            int mid = (left + right) / 2;
            sortMerge(nums, left, mid);
            sortMerge(nums, mid + 1, right);
            merge(nums, left, mid, right);
        }
    }
    
    private void merge(int[] nums, int left, int mid, int right) {
        int[] ret = new int[right - left + 1];
        int p0 = 0, p1 = left, p2 = mid + 1;
        while(p1 <= mid && p2 <= right) {
            if(nums[p1] < nums[p2]) ret[p0++] = nums[p1++];
            else ret[p0++] = nums[p2++];
        }
        
        while(p1 <= mid) ret[p0++] = nums[p1++];
        while(p2 <= right) ret[p0++] = nums[p2++];
        
        for(int i=left ; i<=right ; i++) nums[i] = ret[i - left];
    }
    
    /**  
     * @time  : O(nlog(n))
     * @space : O(nlog(n))
     */
    public int[] quickSort(int[] nums) {
        sortQuick(nums, 0, nums.length);
        return nums;
    }
    
    private void sortQuick(int[] nums, int left, int right) {
        if(left == right || right - left == 1) return;
        
        int pivot = partition(nums, left, right - 1);
        sortQuick(nums, left, pivot);
        sortQuick(nums, pivot + 1, right);
    }
    
    private int partition(int[] nums, int left, int right) {
        int randomNum = (left + right) / 2;
        int pivot = right;
        
        int tmp = nums[randomNum];
        nums[randomNum] = nums[pivot];
        nums[pivot] = tmp;
        
        int placeP = left;
        for(int i=left ; i<right ; i++) {
            if(nums[i] <= nums[pivot]) {
                tmp = nums[placeP];
                nums[placeP] = nums[i];
                nums[i] = tmp;
                
                placeP++;
            }
        }
        
        tmp = nums[pivot];
        nums[pivot] = nums[placeP];
        nums[placeP] = tmp;
        
        return placeP;
    }
}