---
###### tags: `Leetcode`
---
# Leetcode 912. Sort an Array

[link](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 * 104
- -5 * 104 <= nums[i] <= 5 * 104

---

The insertion sort algorithm works by iteratively inserting each element into its correct position within the already sorted portion of the list. In this code, the sorting process begins from the second element (i = 1) and goes up to the last element. For each element, it checks if the element is smaller than the previous element(s) and swaps them until the correct position is reached.

Here's how the code works step by step:

It starts iterating over the list nums from the second element (i = 1). It initializes a variable j with the value of i - 1, which represents the index of the previous element.

It enters a while loop that continues as long as j is greater than or equal to 0 and the element at index j is greater than the next element (nums[j] > nums[j + 1]).
Inside the while loop, it swaps the elements at indices j and j + 1 using a simultaneous assignment.

It decrements j by 1 to compare the current element with the previous element. The while loop continues until either j becomes negative or the element at index j is smaller than or equal to the next element.
After the while loop ends, it moves to the next element and repeats the process.

Finally, it returns the sorted nums list. Overall, the code implements the insertion sort algorithm to sort the given list of integers in ascending order.

#### Solution 1

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        # insertion sort
        for i in range(1, len(nums)):
            j = i - 1
            while j >= 0 and nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
                j -= 1

        return nums 
        

O(T): O(n^2)
O(S): O(1)

---

The merge function is a helper function that merges two sorted subarrays of arr. It takes four parameters: the array arr, the indices L, M, and R. The function divides the array into two subarrays: left from index L to M and right from index M+1 to R. Then, it iterates over the two subarrays, comparing the elements and placing them in the correct order in the original array arr. Finally, it appends any remaining elements from the left or right subarrays to the end of arr.

The mergeSort function is a recursive function that performs the Merge Sort algorithm. It takes three parameters: the array arr, and the indices l and r that represent the left and right boundaries of the subarray being sorted. The function first checks if l and r are equal, which indicates a base case where the subarray has only one element and is already sorted. If not, it calculates the middle index mid and recursively calls mergeSort on the left and right halves of the subarray. Finally, it calls the merge function to merge the two sorted halves into a single sorted subarray.

The sortArray method initializes the merge sort process by calling mergeSort on the entire input array nums, passing the initial left and right boundaries as 0 and len(nums) - 1 respectively. The sorted array is then returned as the result.

#### Solution 2

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def merge(arr, L, M, R):
            left, right = arr[L:M+1], arr[M+1:R+1]
            i, j, k = L, 0, 0
            
            while j < len(left) and k < len(right):
                if left[j] < right[k]:
                    arr[i] = left[j]
                    j += 1
                else:
                    arr[i] = right[k]
                    k += 1                   
                i += 1

            while j < len(left):
                arr[i] = left[j]
                j += 1
                i += 1

            while k < len(right):
                arr[i] = right[k]
                k += 1
                i += 1


        def mergeSort(arr, l, r):
            if l == r:
                return arr

            mid = (l + r) // 2
            mergeSort(arr, l, mid)
            mergeSort(arr, mid + 1, r)
            merge(arr, l, mid, r)

            return arr

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

O(T): O(nlog(n))
O(S): O(n)

---

#### Solution 3

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def quickSort(arr, s, e):
            if len(arr) == 1:
                return arr
                
            if e - s + 1 <= 1:
                return

            pivot = arr[e]
            left = s
    
            for i in range(s, e):
                if arr[i] < pivot:
                    tmp = arr[left]
                    arr[left] = arr[i]
                    arr[i] = tmp
                    left += 1

            arr[e] = arr[left]
            arr[left] = pivot

            quickSort(arr, s, left - 1)
            quickSort(arr, left + 1, e)

            return arr

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

O(T): worst: O(n^2), O(nlog(n))
O(S): O(1)