Skip to main content
CodePeetCodePeet
CodePeet 250

Sort an Array

MEDIUMProblemSolveExternal Links

Description

You are given an array of integers called nums. Your task is to sort this array in ascending order (from smallest to largest) and return the sorted array.

There is an important constraint: you are not allowed to use any built-in sorting functions provided by your programming language. You must implement the sorting algorithm yourself, and it must run in O(n log n) time complexity while using the smallest amount of extra space possible.

This problem tests your understanding of efficient sorting algorithms such as Merge Sort, Heap Sort, or Quick Sort — algorithms that achieve O(n log n) performance through divide-and-conquer or heap-based strategies.

Examples

Example 1

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

Output: [1, 2, 3, 5]

Explanation: After sorting, the elements are rearranged into ascending order. The values 2 and 3 happen to stay in the same relative positions, while 1 moves to the front and 5 moves to the end.

Example 2

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

Output: [0, 0, 1, 1, 2, 5]

Explanation: The array contains duplicate values (two 0s and two 1s). A correct sorting algorithm must handle duplicates properly, placing them adjacent to each other in the final sorted order.

Example 3

Input: nums = [1]

Output: [1]

Explanation: A single-element array is already sorted. Any correct sorting algorithm should handle this edge case without error.

Constraints

  • 1 ≤ nums.length ≤ 5 × 10^4
  • -5 × 10^4 ≤ nums[i] ≤ 5 × 10^4

Editorial

Brute Force

Intuition

The simplest way to sort an array is Selection Sort. The idea is very natural: find the smallest element in the entire array and place it at the beginning, then find the smallest element among the remaining unsorted portion and place it next, and so on.

Think of it like organizing a hand of playing cards. You scan all your cards, find the lowest one, and move it to the left. Then you scan the remaining cards for the next lowest, and place it next to the first. You repeat until all cards are in order.

For each position in the array, we search the rest of the array for the minimum value and swap it into place. This requires two nested loops: the outer loop picks each position, and the inner loop finds the minimum in the unsorted portion.

Step-by-Step Explanation

Let's trace through with nums = [5, 2, 3, 1]:

Step 1: Start with i=0. We need to find the minimum element in the entire array [5, 2, 3, 1].

Step 2: Scan from index 1 to 3. The minimum value is 1 at index 3.

Step 3: Swap nums[0] and nums[3]. Array becomes [1, 2, 3, 5]. Position 0 is now sorted.

Step 4: Move to i=1. Find the minimum in the unsorted portion [2, 3, 5].

Step 5: Scan from index 2 to 3. The minimum is 2 at index 1 (already in place). No swap needed.

Step 6: Move to i=2. Find the minimum in the unsorted portion [3, 5].

Step 7: Scan index 3. The minimum is 3 at index 2 (already in place). No swap needed.

Step 8: i=3 is the last element — it's automatically in the correct position.

Result: [1, 2, 3, 5]

Selection Sort — Finding and Placing Minimums — Watch how Selection Sort repeatedly finds the minimum element from the unsorted portion and swaps it into the correct position at the front.

Algorithm

  1. For each index i from 0 to n-2:
    a. Set min_idx = i
    b. For each index j from i+1 to n-1:
    • If nums[j] < nums[min_idx], update min_idx = j
      c. Swap nums[i] and nums[min_idx]
  2. Return the sorted array

Code

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (nums[j] < nums[minIdx]) {
                    minIdx = j;
                }
            }
            swap(nums[i], nums[minIdx]);
        }
        return nums;
    }
};
class Solution:
    def sortArray(self, nums: list[int]) -> list[int]:
        n = len(nums)
        for i in range(n - 1):
            min_idx = i
            for j in range(i + 1, n):
                if nums[j] < nums[min_idx]:
                    min_idx = j
            nums[i], nums[min_idx] = nums[min_idx], nums[i]
        return nums
class Solution {
    public int[] sortArray(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (nums[j] < nums[minIdx]) {
                    minIdx = j;
                }
            }
            int temp = nums[i];
            nums[i] = nums[minIdx];
            nums[minIdx] = temp;
        }
        return nums;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n-1 times. For each iteration i, the inner loop scans n-i-1 elements. The total comparisons are (n-1) + (n-2) + ... + 1 = n(n-1)/2, which is O(n²).

Space Complexity: O(1)

Selection Sort operates in-place using only a few integer variables (i, j, min_idx, temp). No additional memory proportional to input size is required.

Why This Approach Is Not Efficient

Selection Sort has O(n²) time complexity. With n up to 5 × 10^4, this means up to ~1.25 × 10^9 comparisons — far too slow for any reasonable time limit (typically 10^7–10^8 operations per second).

The core issue is that Selection Sort does redundant work. Each pass scans the entire unsorted portion linearly to find the minimum. It never leverages any structure or ordering information from previous passes.

To achieve the required O(n log n) time, we need a fundamentally different strategy. The divide-and-conquer approach splits the problem into smaller subproblems, solves them independently, and then efficiently combines the results. Merge Sort is a classic example: instead of scanning for the minimum n times, it splits the array in half, sorts each half recursively, and then merges the two sorted halves in linear time.

Optimal Approach - Merge Sort

Intuition

Merge Sort follows the divide-and-conquer paradigm, which breaks a large problem into smaller pieces, solves each piece, and then combines the solutions.

Imagine you have a messy pile of exam papers to sort by student name. Instead of scanning through the entire pile repeatedly (like Selection Sort), you split the pile in half, give each half to a friend, and ask them to sort their half. Once both halves are sorted, you combine them by taking the alphabetically-first paper from whichever pile has it, alternating between the two sorted piles. This merge step is fast because both halves are already in order — you only need to compare the front of each pile.

The key insight is that merging two already-sorted arrays is a simple O(n) operation. And by recursively halving the array, we only need log(n) levels of merging, giving us O(n log n) total work.

Merge Sort works in three phases:

  1. Divide: Split the array into two halves
  2. Conquer: Recursively sort each half
  3. Combine: Merge the two sorted halves into one sorted array
Merge sort divide-and-conquer tree showing array [5, 2, 3, 1] being split and merged back
Merge sort divide-and-conquer tree showing array [5, 2, 3, 1] being split and merged back

Step-by-Step Explanation

Let's trace through the merge step with two sorted halves: left = [2, 5] and right = [1, 3]. We need to merge them into a single sorted array.

Step 1: Initialize three pointers — i=0 for the left array, j=0 for the right array, and k=0 for the result position. Result array is empty.

Step 2: Compare left[0]=2 with right[0]=1. Since 1 < 2, place 1 into result. Advance j to 1. Result: [1].

Step 3: Compare left[0]=2 with right[1]=3. Since 2 < 3, place 2 into result. Advance i to 1. Result: [1, 2].

Step 4: Compare left[1]=5 with right[1]=3. Since 3 < 5, place 3 into result. Advance j to 2. Result: [1, 2, 3].

Step 5: Right array is exhausted (j=2 is past the end). Copy remaining left elements: place 5 into result. Result: [1, 2, 3, 5].

Step 6: Both arrays fully consumed. The merged result [1, 2, 3, 5] is the fully sorted array.

Merge Sort — Merging Two Sorted Halves [2, 5] and [1, 3] — Watch the merge operation combine two sorted subarrays into one sorted result by repeatedly picking the smaller front element from either half.

Algorithm

  1. Base case: If the array has 0 or 1 elements, return it (already sorted)
  2. Divide: Find the midpoint mid = (left + right) / 2
  3. Conquer: Recursively sort the left half arr[left..mid]
  4. Conquer: Recursively sort the right half arr[mid+1..right]
  5. Merge: Combine the two sorted halves:
    a. Create temporary arrays for left and right halves
    b. Use three pointers (i, j, k) to compare front elements and place the smaller one into the result
    c. Copy any remaining elements from the non-exhausted half
  6. Return the sorted array

Code

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }
    
private:
    void mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) return;
        
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
    
    void merge(vector<int>& nums, int left, int mid, int right) {
        vector<int> temp;
        int i = left, j = mid + 1;
        
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp.push_back(nums[i]);
                i++;
            } else {
                temp.push_back(nums[j]);
                j++;
            }
        }
        
        while (i <= mid) {
            temp.push_back(nums[i]);
            i++;
        }
        
        while (j <= right) {
            temp.push_back(nums[j]);
            j++;
        }
        
        for (int k = left; k <= right; k++) {
            nums[k] = temp[k - left];
        }
    }
};
class Solution:
    def sortArray(self, nums: list[int]) -> list[int]:
        if len(nums) <= 1:
            return nums
        
        mid = len(nums) // 2
        left = self.sortArray(nums[:mid])
        right = self.sortArray(nums[mid:])
        
        return self.merge(left, right)
    
    def merge(self, left: list[int], right: list[int]) -> list[int]:
        result = []
        i = j = 0
        
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        
        result.extend(left[i:])
        result.extend(right[j:])
        
        return result
class Solution {
    public int[] sortArray(int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }
    
    private void mergeSort(int[] nums, int left, int right) {
        if (left >= right) return;
        
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
    
    private void merge(int[] nums, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
        
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        
        while (j <= right) {
            temp[k++] = nums[j++];
        }
        
        for (int p = 0; p < temp.length; p++) {
            nums[left + p] = temp[p];
        }
    }
}

Complexity Analysis

Time Complexity: O(n log n)

The array is recursively divided in half, creating log(n) levels of recursion. At each level, the merge operations collectively process all n elements exactly once. Therefore, total work = n elements × log(n) levels = O(n log n). This holds for best, average, and worst cases — Merge Sort's performance is consistent regardless of input order.

Space Complexity: O(n)

The merge step requires a temporary array to hold the merged result. At any point during recursion, the largest temporary array needed is proportional to n (when merging the final two halves). Additionally, the recursion stack uses O(log n) space. Combined: O(n) + O(log n) = O(n).