912. Sort an Array

# Medium, DFS

Solution 1(Merge sort): standard Divide & Conquer

先局部有序，整体有序

1. consider edge case( return or stop condition )

2. divide into two equal parts to do sort, store into two lists

3. merge two lists and return the list

class Solution:
    # merge sort
    def sortArray(self, nums: List[int]) -> List[int]:
        # condier edge case
        if len(nums) <= 1:
            return nums
        
        # divide
        l = len(nums)
        a = self.sortArray(nums[:l//2])
        b = self.sortArray(nums[l//2:])
        
        # combine
        i, j, x = 0, 0, 0
        while i < len(a) and j < len(b):
            if a[i] <= b[j]:
                nums[x] = a[i]
                i = i+1
            else:
                nums[x] = b[j]
                j = j+1
            x = x+1
        
        while i < len(a):
            nums[x] = a[i]
            x = x+1
            i = i+1
            
        while j < len(b):
            nums[x] = b[j]
            x = x+1
            j = j+1

        return nums

Its best, worst and avearge time complexities are the same: $O(NlgN)$ , N is the numbers of elements. $T(n) = 2*T(n-1) + \theta(n) ==> T = O(NlgN)+O(n) = O(NlgN)$ . This can be proved by Binary Tree.

Disadvantage: extra $O(n)$ space

Advantage: time complexity is stable, no matter best or worst case. It has stability. For example, [1, 3, 3]. Two elements are the same, but after sort, the two 3 positions won't change.

Solution 2(Quick sort): kind of Divide & Conquer

先宏观有序，再微观有序

1. Partition: choose last element as the pivot, separate the list into two parts. Left elements are smaller than pivot, right elements are bigger than pivot. Return the index of pivot.

2. Quick sort: sort left part and sort right part separately.

3. Implement in sortArray( main function )

Java

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }
    
    public void quickSort(int[] nums, int left, int right) {
        // stop condition
        if(left >= right) return;
        
        // regular
        int index = pivot(nums, left, right);
        
        quickSort(nums, left, index - 1);
        quickSort(nums, index + 1, right);
    }
    
    private int pivot(int[] nums, int left, int right) {
        // stop condition
        if(left == right) return left;
        
        // regular
        int i = left;
        int pivot = nums[right];
        for(int j = left; j < right; j ++) {
            if(nums[j] < pivot) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                i ++;
            }
        }
        int temp = nums[i];
        nums[i] = nums[right];
        nums[right] = temp;
        
        return i;
    }
}

Python

class Solution:
    # quick sort
    def pivot(self, nums, left, right):
        pivot = nums[right]
        i = left
        for j in range(left, right):
            if nums[j] < pivot:
                nums[i], nums[j] = nums[j], nums[i]
                i = i+1
        nums[i], nums[right] = nums[right], nums[i]
        return i
        
    def quickSort(self, nums, left, right):
        # stop condition
        if left > right:
            return
        
        # regular case
        i = self.pivot(nums, left, right)
        self.quickSort(nums, left, i-1)
        self.quickSort(nums, i+1, right)
        
        
    def sortArray(self, nums: List[int]) -> List[int]:
        # consider edge case
        if len(nums) <= 1:
            return nums
        
        # regular case
        self.quickSort(nums, 0, len(nums)-1)
        return nums

Can't do quick sort only in function sortArray, because one parameter is not enough. 对于快排来说，拆解成找到pivot ，和分别对pivot两边排序。为什么quickSort不能直接放在sortArray里面呢？因quickSort依然属于recursive类型，将大问题拆解成小问题，然后迭代解决小问题，因此结果是直接放在参数里，而不是return，但是sortArray必须要返回结果，所以sortArray不能是quickSort。

Worst time complexity = $O(n^2)$ , when the array is descending.

Best time complexity = $O(n)$ , when the array is ascending.

Avarage time complexity = $O(nlgn)$.

总结一下：

Recursive其实是自上而下将大问题拆分长小问题，是一层层迭代，参数里直接带着result，所以终止情况return空。

Divide & Conquer其实是将大问题看作若干个重复的小问题，解决小问题，再合起来，直接return结果。

因此分析题目时，先搞清楚要用recursive还是divide & conquer。