912.Sort an Array
===

###### tags: `Medium`,`Array`,`Sorting`

[912. Sort an Array](https://leetcode.com/problems/sort-an-array/)

### 題目描述

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** functions in `O(nlog(n))` time complexity and with the smallest space complexity possible.

### 範例

**Example 1:**

Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).

**Example 2:**

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Explanation: Note that the values of nums are not necessairly unique.

**Constraints**:

* 1 <= `nums.length` <= 5 * 10^4^
* -5 * 10^4^ <= `nums[i]` <= 5 * 10^4^

### 解答

#### Javascript

function sortArray(nums) {
  if (nums.length <= 1) return nums;

  const mid = ~~(nums.length / 2);
  const left = nums.slice(0, mid);
  const right = nums.slice(mid);

  return merge(sortArray(left), sortArray(right));
}

function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  result.push(...left.slice(leftIndex));
  result.push(...right.slice(rightIndex));

  return result;
}

> 寫個merge sort好了比較簡單。
> [name=Marsgoat][time=Mar 1, 2023]

#### Python

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def quickSort(left, right):
            if left >= right:
                return

            l, r = left, right
            mid = (r - l) // 2 + l
            pivot = nums[mid]

            while r >= l:
                while r >= l and nums[l] < pivot: l += 1
                while r >= l and nums[r] > pivot: r -= 1
                if r >= l:
                    nums[l], nums[r] = nums[r], nums[l]
                    l += 1
                    r -= 1

            quickSort(left, r)
            quickSort(l, right)

        quickSort(0, len(nums) - 1)
        
        return nums

> [name=Ron Chen][time=Thu, Mar 2, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)