_912. Sort an Array.md

912. Sort an Array

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 25, 2024

Last updated : July 25, 2024

---

Related Topics : Array, Divide and Conquer, Sorting, Heap (Priority Queue), Merge Sort, Bucket Sort, Radix Sort, Counting Sort

Acceptance Rate : 57.02 %

---

Solutions

• m912 Merge Sort Daily.java
• m912 Merge Sort Daily.py

Java

m912 Merge Sort Daily.java

class Solution {
    public int[] sortArray(int[] nums) {
        return mergeSort(nums);
    }

    private int[] mergeSort(int[] nums) {
        if (nums.length <= 1) {
            return nums;
        }

        int[] left = mergeSort(Arrays.copyOfRange(nums, 0, nums.length / 2));
        int[] right = mergeSort(Arrays.copyOfRange(nums, nums.length / 2, nums.length));

        int leftIndx = 0, rightIndx = 0;
        int i = 0;
        while (leftIndx < left.length && rightIndx < right.length) {
            if (left[leftIndx] < right[rightIndx]) {
                nums[i] = left[leftIndx];
                ++leftIndx;
            } else {
                nums[i] = right[rightIndx];
                ++rightIndx;
            }
            ++i;
        }

        while (leftIndx < left.length) {
            nums[i] = left[leftIndx];
            ++leftIndx;
            ++i;
        }
        while (rightIndx < right.length) {
            nums[i] = right[rightIndx];
            ++rightIndx;
            ++i;
        }
        return nums;
    }
}

Python

m912 Merge Sort Daily.py

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def mergeSort(nums: List[int]) -> List[int] :
            if len(nums) <= 1 :
                return nums
            
            left = mergeSort(nums[:len(nums) // 2])
            right = mergeSort(nums[len(nums) // 2:])
            leftIndx = 0
            rightIndx = 0

            output = []

            while leftIndx < len(left) and rightIndx < len(right) :
                if left[leftIndx] < right[rightIndx] :
                    output.append(left[leftIndx])
                    leftIndx += 1
                else :
                    output.append(right[rightIndx])
                    rightIndx += 1

            output.extend(left[leftIndx:])
            output.extend(right[rightIndx:])

            return output
        return mergeSort(nums)