Log inSign up
mediumLeetCodeNot Started

Sort an Array

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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(n log(n)) time complexity and with the smallest practical space complexity.

Example 1 · Standard Unsorted Array:

Input: nums = [5, 2, 3, 1]
Output: [1, 2, 3, 5]
Explanation: Array sorted in non-decreasing order.

Example 2 · Array with Duplicates and Negatives:

Input: nums = [5, 1, 1, 2, 0, 0]
Output: [0, 0, 1, 1, 2, 5]
Explanation: Duplicates and zeroes placed correctly.

Constraints:

  • 1 <= nums.length <= 5 * 104
  • -5 * 104 <= nums[i] <= 5 * 104

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Divide and Conquer recursion
  • Two-pointer merge subroutine
  • Heap data structure & sift-down mechanics

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Implement Merge Sort recursion and merge subroutines from scratch.
  • Understand the Master Theorem T(N) = 2T(N/2) + O(N) -> O(N log N).
  • Prevent memory thrashing by reusing auxiliary buffer arrays during merge.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • Use Merge Sort for stable guaranteed O(N log N).
  • Use Heap Sort for in-place O(N log N) with O(1) auxiliary space.
  • Avoid naive QuickSort without 3-way partitioning to avoid O(N2) TLE.

Connected Patterns:

Sort Colors (Dutch National Flag)Kth Largest Element in an Array

1. Selection Sort (Brute Force)

Intuition

For each index i from 0 to n-1: find the index minIdx of the minimum element in nums[i..n-1]. Swap nums[i] with nums[minIdx]. Takes O(n2) time.

When to apply: Use for pedagogical baseline of in-place comparison sorts.

Selection Sort Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [5, 2, 3, 1]
Current operationSTEP 1 OF 6
Array: [5, 2, 3, 1]
Visual state
Values and pointers at this exact step
array
S
1
2
3
5
0
↑ Locked 1
1
2
3
Variables at this step
i
0
minIdx
3
arr
[1,2,3,5]
Check / comparison
min element is 1 at index 3
Decision / next transition
Swap nums[0] (5) and nums[3] (1). Array becomes [1, 2, 3, 5].
Why this step matters

Array: [5, 2, 3, 1]. i = 0. Find minimum in nums[0..3].

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int[] sortArray(int[] nums) {
4 int n = nums.length;
5 for (int i = 0; i < n - 1; i++) {
6 int minIdx = i;
7 for (int j = i + 1; j < n; j++) {
8 if (nums[j] < nums[minIdx]) minIdx = j;
9 }
10 int temp = nums[i];
11 nums[i] = nums[minIdx];
12 nums[minIdx] = temp;
13 }
14 return nums;
15 }
16 }
17
18 public static void main(String[] args) {
19 Solution sol = new Solution();
20 int[] nums = {5, 2, 3, 1};
21 System.out.println("Sorted Array: " + java.util.Arrays.toString(sol.sortArray(nums)));
22 }
23}

Time & Space Complexity

  • Time complexity: O(n^2) — n*(n-1)/2 comparisons in the worst case.
  • Space complexity: O(1) — O(1) auxiliary variables.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Quick Sort with Random Pivot (Better)

Intuition

Quick sort chooses a random pivot element, partitions the array such that elements smaller than pivot are on the left and larger are on the right, and recursively sorts both halves.

When to apply: Use to understand partition-exchange sorting and in-place divide-and-conquer.

Quick Sort Partition Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [5, 2, 3, 1]
Current operationSTEP 1 OF 6
Array: [5, 2, 3, 1]
Visual state
Values and pointers at this exact step
pointers
S
5
2
3
1
0
1
2
↑ Pivot=3
3
Variables at this step
pivot
3
Check / comparison
pivot = 3
Decision / next transition
Partition elements around 3.
Why this step matters

Array: [5, 2, 3, 1]. Pick pivot = 3 at index 2.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.Random;
2
3public class Main {
4 public static class Solution {
5 private Random rand = new Random();
6
7 public int[] sortArray(int[] nums) {
8 quickSort(nums, 0, nums.length - 1);
9 return nums;
10 }
11
12 private void quickSort(int[] nums, int l, int r) {
13 if (l >= r) return;
14 int pivotIdx = l + rand.nextInt(r - l + 1);
15 int pivot = nums[pivotIdx];
16 swap(nums, pivotIdx, r);
17
18 int i = l;
19 for (int j = l; j < r; j++) {
20 if (nums[j] < pivot) {
21 swap(nums, i, j);
22 i++;
23 }
24 }
25 swap(nums, i, r);
26
27 quickSort(nums, l, i - 1);
28 quickSort(nums, i + 1, r);
29 }
30
31 private void swap(int[] nums, int i, int j) {
32 int t = nums[i];
33 nums[i] = nums[j];
34 nums[j] = t;
35 }
36 }
37
38 public static void main(String[] args) {
39 Solution sol = new Solution();
40 int[] nums = {5, 2, 3, 1};
41 System.out.println("Sorted Array: " + java.util.Arrays.toString(sol.sortArray(nums)));
42 }
43}

Time & Space Complexity

  • Time complexity: O(n log n) average, O(n^2) worst — Random pivot choices guarantee O(n log n) expected time across all input permutations.
  • Space complexity: O(log n) recursion stack — O(log n) recursion stack frames.

3. Merge Sort (Optimal & Guaranteed O(n log n))

Intuition

Recursively split the array in half until base cases of size 1 are reached. Merge the two sorted halves into a temporary buffer using two pointers, copying the merged sorted result back into nums.

When to apply: Use as the optimal standard sorting algorithm with predictable O(n log n) performance.

Merge Sort Divide-and-Conquer Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [5, 2, 3, 1]
Current operationSTEP 1 OF 6
Step 1: Divide [5, 2, 3, 1] at mid = 1 into left [5, 2] and right [3, 1]
Visual state
Values and pointers at this exact step
pointers
S
5
2
3
1
0
↑ Left half
1
2
3
Variables at this step
left
[5,2]
right
[3,1]
Check / comparison
Split into 2 halves.
Decision / next transition
Recursively sort left [5, 2].
Why this step matters

Step 1: Divide [5, 2, 3, 1] at mid = 1 into left [5, 2] and right [3, 1].

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int[] sortArray(int[] nums) {
4 mergeSort(nums, 0, nums.length - 1, new int[nums.length]);
5 return nums;
6 }
7
8 private void mergeSort(int[] nums, int l, int r, int[] temp) {
9 if (l >= r) return;
10 int mid = l + (r - l) / 2;
11 mergeSort(nums, l, mid, temp);
12 mergeSort(nums, mid + 1, r, temp);
13 merge(nums, l, mid, r, temp);
14 }
15
16 private void merge(int[] nums, int l, int mid, int r, int[] temp) {
17 int i = l, j = mid + 1, k = l;
18 while (i <= mid && j <= r) {
19 if (nums[i] <= nums[j]) temp[k++] = nums[i++];
20 else temp[k++] = nums[j++];
21 }
22 while (i <= mid) temp[k++] = nums[i++];
23 while (j <= r) temp[k++] = nums[j++];
24 for (int p = l; p <= r; p++) nums[p] = temp[p];
25 }
26 }
27
28 public static void main(String[] args) {
29 Solution sol = new Solution();
30 int[] nums = {5, 2, 3, 1};
31 System.out.println("Sorted Array: " + java.util.Arrays.toString(sol.sortArray(nums)));
32 }
33}

Time & Space Complexity

  • Time complexity: O(n log n) — The tree depth is log2(n), with each level doing O(n) total work during merges.
  • Space complexity: O(n) — O(n) auxiliary memory for the temporary merge buffer.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Insertion / Selection SortO(N^2)O(1)Compare every pair and shift elements one by one.Quadratic number of comparisons and shifts.
2.Better — Randomized Quick Sort (3-Way Partition)O(N log N) average, O(N^2) worstO(log N) stackPick random pivot, 3-way partition into (<, ==, >), recurse.Worst-case pivot selection.
3.Optimal — Merge SortOptimalO(N log N) guaranteedO(N)Divide array into halves, recursively sort, and merge two sorted halves.None; industry gold standard for guaranteed logarithmic depth.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Empty or Single Element Array — Handle minimal input sizes (N = 0 or N = 1) cleanly without out-of-bounds errors.
  • Duplicate Elements — Verify behavior when all elements are identical (e.g. all 0s or all equal values).
  • Extreme Numerical Values — Account for maximum/minimum allowed constraint values (-109 to 109) to prevent overflow.
  • Boundary Conditions — Ensure correct execution when target or match is located at the first or last index.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Sort an Array?

2.Why is the brute force approach suboptimal for large inputs in Sort an Array?

3.Which data structure or technique enables the optimal solution for Sort an Array?

Back to DSA Sheet