---
tags: data_structure_python
---

# Sort an array <img src="https://img.shields.io/badge/-easy-brightgreen">

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

Example 1:

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

Example 2:

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

**Constraints:**

- 1 <= nums.length <= 50000
- -50000 <= nums[i] <= 50000

# Solution

### Solution 1: Recursive Merge sort (top down approach)

- DFS-like code.

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        # Merge sort.
        if len(nums) == 1:
            return nums
        else:
            pivot = len(nums)//2
            left = self.sortArray(nums[:pivot])
            right = self.sortArray(nums[pivot:])
            return self.merge(left, right)
            
    def merge(self, left, right):
        res, i, j = [], 0, 0
        
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                res.append(left[i])
                i += 1
            else:
                res.append(right[j])
                j += 1
        
        while i < len(left):
            res.append(left[i])
            i += 1
        
        while j < len(right):
            res.append(right[j])
            j += 1
            
        return res

### Solution 2: Iterative Merge sort (bottom up approach)

- BFS-like code.

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        # Merge sort.
        queue = [[elt] for elt in nums]
        while len(queue) > 1:
            X = queue.pop(0)
            Y = queue.pop(0)    
            newBlock = self.mergesort(X, Y)
            queue.append(newBlock)
        return queue.pop()
            
    def mergesort(self, X, Y):
        newBlock, i, j = [], 0, 0
        
        while i < len(X) and j < len(Y):
            if X[i] < Y[j]:
                newBlock.append(X[i])
                i += 1
            else:
                newBlock.append(Y[j])
                j += 1
                
        while i < len(X):
            newBlock.append(X[i])
            i += 1
            
        while j < len(Y):
            newBlock.append(Y[j])
            j += 1
        
        return newBlock