# 912. Sort an Array

### Solution 1(Merge sort): standard Divide & Conquer

{% hint style="success" %}
先局部有序，整体有序
{% endhint %}

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

```python
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

{% hint style="success" %}
先宏观有序，再微观有序
{% endhint %}

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 )

{% tabs %}
{% tab title="Java" %}

```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;
    }
}
```

{% endtab %}

{% tab title="Python" %}

```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


```

{% endtab %}
{% endtabs %}

{% hint style="danger" %}
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。
{% endhint %}

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)$$.&#x20;

> 总结一下：
>
> Recursive其实是自上而下将大问题拆分长小问题，是一层层迭代，参数里直接带着result，所以终止情况return空。
>
> Divide & Conquer其实是将大问题看作若干个重复的小问题，解决小问题，再合起来，直接return结果。
>
> 因此分析题目时，先搞清楚要用recursive还是divide & conquer。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://r24zeng.gitbook.io/leetcode-notebook/wan-quan-an-zhao-jiu-zhang-suan-fa-shua-de-60-dao-zuo-you/iii.-binary-tree/912.-sort-an-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.