LeetCode 912: Sort an Array Solution

Master LeetCode problem 912 (Sort an Array), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

912. Sort an Array

Medium

Array Divide and Conquer Sorting Heap (Priority Queue)Merge Sort Bucket Sort Radix Sort Counting Sort

Problem Explanation

Explanation

To sort the given array of integers in ascending order without using any built-in functions, we can implement the Merge Sort algorithm. Merge Sort is a divide and conquer algorithm that recursively divides the array into smaller subarrays, sorts them, and then merges them back together.

Divide: Divide the array into two halves.
Conquer: Recursively sort the two halves.
Combine: Merge the two sorted halves back together.

The time complexity of Merge Sort is O(nlog(n)), where n is the number of elements in the array. The space complexity is O(n) due to the need for auxiliary space during the merge step.

Solution Code

class Solution {
    public int[] sortArray(int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }
    
    private void mergeSort(int[] nums, int low, int high) {
        if (low < high) {
            int mid = low + (high - low) / 2;
            mergeSort(nums, low, mid);
            mergeSort(nums, mid + 1, high);
            merge(nums, low, mid, high);
        }
    }
    
    private void merge(int[] nums, int low, int mid, int high) {
        int[] temp = new int[nums.length];
        int i = low, j = mid + 1, k = low;
        
        while (i <= mid && j <= high) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
        
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        
        while (j <= high) {
            temp[k++] = nums[j++];
        }
        
        for (i = low; i <= high; i++) {
            nums[i] = temp[i];
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 912 (Sort an Array)?

This page provides optimized solutions for LeetCode problem 912 (Sort an Array) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 912 (Sort an Array)?

The time complexity for LeetCode 912 (Sort an Array) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 912 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 912 in Java, C++, or Python.

Back to LeetCode Solutions