Sort an Array solution and explanation
Google
TCS
Infosys
9 more videos on this problem
Sort an Array - Leetcode 912 - PythonNeetCodeIO · 17:13 · 79K views
Sort an Array | Leetcode 912 | codestorywithMIKcodestorywithMIK · 10:08 · 11K views
Leetcode | 912. Sort an Array | Medium | Java Solution [Counting Sort]Developer Docs · 11:56 · 5K views
Merge Sort Fundamentals | LeetCode 912 Sort An Arrayleetuition · 13:36 · 2K views
LEETCODE 912 SORT AN ARRAY PYTHON | how to do merge sortSasa codes · 9:10 · 1K views
912. Sort an Array (python) (Leetcode Medium)Programming Live with Larry · 3:29 · 965 views
912. Sort an Array - JAVA (Min Heap / Merge sort / Counting sort - Detailed explanation + Coding)Sourin Majumdar · 22:47 · 812 views
Leetcode 912. Sort an ArrayLeetcode Lab · 18:49 · 771 views
Daily Leetcode #1065: Mar 01, 2023 - 912. Sort an ArrayProgramming Live with Larry · 13:23 · 721 views
Leetcode 912. Sort an Array, Merge SortNeedCode⚡ · 11:29 · 511 views
The problem
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(nlog(n)) time complexity and with the smallest space complexity possible.
Example 1:
Input: nums = [5,2,3,1] Output: [1,2,3,5] Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).
Example 2:
Input: nums = [5,1,1,2,0,0] Output: [0,0,1,1,2,5] Explanation: Note that the values of nums are not necessairly unique.
Constraints:
1 <= nums.length <= 5 * 104-5 * 104 <= nums[i] <= 5 * 104
Approach overview
Problem Overview: Given an integer array nums, return the array sorted in ascending order. Built-in sorting functions are usually restricted in interview settings, so you are expected to implement an efficient comparison-based sorting algorithm yourself.
Approach 1: Merge Sort (O(n log n) time, O(n) space)
Divide and Conquer works well for sorting because the array can be recursively split into smaller pieces. Merge Sort divides the array into two halves until each subarray has one element. During the merge step, two sorted halves are combined by repeatedly comparing the smallest remaining elements. Each level processes all n elements and the recursion depth is log n, giving O(n log n) time. The tradeoff is additional memory: merging requires a temporary array of size n. Use this approach when you want stable sorting and predictable performance.
Approach 2: Quick Sort (Hoare Partition) (Average O(n log n) time, O(log n) space)
Quick Sort selects a pivot and partitions the array so elements smaller than the pivot move left and larger elements move right. Hoare's partition scheme uses two pointers moving inward from both ends and swaps out-of-place elements. After partitioning, recursively sort the left and right segments. The average time complexity is O(n log n), while recursion stack space is about O(log n). Worst-case time can degrade to O(n^2) if pivots are poorly chosen, but random inputs usually avoid this. This approach is common in production sorting implementations because it has strong cache performance and low memory usage.
Approach 3: Counting / Radix Style Sorting (O(n + k) time)
If the integer range is limited, non-comparison algorithms can be faster than traditional sorting. Counting Sort counts the frequency of each value and reconstructs the array in order, giving linear complexity O(n + k) where k is the value range. Radix Sort extends this idea by sorting digits from least significant to most significant. These techniques rely on bucket-style grouping and are often discussed with sorting optimizations for numeric arrays. They are less common in interviews unless constraints make the value range small.
Recommended for interviews: Merge Sort and Quick Sort are the expected solutions. Implementing Merge Sort demonstrates strong understanding of divide and conquer and guarantees O(n log n) time. Quick Sort is often preferred when interviewers want an in-place algorithm with lower extra space. Showing both approaches proves you understand core array sorting fundamentals.
Approach 1: Merge Sort
Merge Sort is a classic divide-and-conquer sorting algorithm that works in O(nlog(n)) time complexity and requires extra space proportional to the length of the array. The core concept is to divide the array into two halves, recursively sort each half, and then merge the sorted halves to produce a sorted array.
def merge(arr, left, mid, right):
n1 = mid - left + 1
n2 = right - mid
L = arr[left:left + n1]
R = arr[mid + 1:mid + 1 + n2]
i = j = 0
k = left
while i < n1 and j < n2:
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < n1:
arr[k] = L[i]
i += 1
k += 1
while j < n2:
arr[k] = R[j]
j += 1
k += 1
def merge_sort(arr, left, right):
if left < right:
mid = (left + right) // 2
merge_sort(arr, left, mid)
merge_sort(arr, mid + 1, right)
merge(arr, left, mid, right)
nums = [5, 2, 3, 1]
merge_sort(nums, 0, len(nums) - 1)
print(nums)import java.util.Arrays;
public class MergeSort {
public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
public static void main(String[] args) {
int[] nums = {5, 2, 3, 1};
mergeSort(nums, 0, nums.length - 1);
System.out.println(Arrays.toString(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
vector<int> L(n1), R(n2);
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
int main() {
vector<int> nums = {5, 2, 3, 1};
mergeSort(nums, 0, nums.size() - 1);
for (int num : nums)
cout << num << " ";
return 0;
}function merge(arr, left, mid, right) {
let n1 = mid - left + 1;
let n2 = right - mid;
let L = arr.slice(left, left + n1);
let R = arr.slice(mid + 1, mid + 1 + n2);
let i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
while (i < n1) {
arr[k++] = L[i++];
}
while (j < n2) {
arr[k++] = R[j++];
}
}
function mergeSort(arr, left, right) {
if (left < right) {
let mid = Math.floor((left + right) / 2);
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
let nums = [5, 2, 3, 1];
mergeSort(nums, 0, nums.length - 1);
console.log(nums);#include <stdio.h>
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
int main() {
int nums[] = {5, 2, 3, 1};
int length = sizeof(nums) / sizeof(nums[0]);
mergeSort(nums, 0, length - 1);
for (int i = 0; i < length; i++)
printf("%d ", nums[i]);
return 0;
}using System;
class MergeSort {
static void Merge(int[] array, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] leftArray = new int[n1];
int[] rightArray = new int[n2];
Array.Copy(array, left, leftArray, 0, n1);
Array.Copy(array, mid + 1, rightArray, 0, n2);
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArray[i] <= rightArray[j]) {
array[k++] = leftArray[i++];
} else {
array[k++] = rightArray[j++];
}
}
while (i < n1) {
array[k++] = leftArray[i++];
}
while (j < n2) {
array[k++] = rightArray[j++];
}
}
static void MergeSortRec(int[] array, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
MergeSortRec(array, left, mid);
MergeSortRec(array, mid + 1, right);
Merge(array, left, mid, right);
}
}
static void Main() {
int[] nums = {5, 2, 3, 1};
MergeSortRec(nums, 0, nums.Length - 1);
Console.WriteLine(string.Join(" ", nums));
}
}The Python version implements merge sort smoothly with Python's slicing and operations. The recursive function merge_sort splits and calls merge to organize the sections of the list during the sort process.
Time Complexity: O(nlog(n))
Space Complexity: O(n)
Approach 2: Quick Sort (Hoare's Partition Scheme)
Quick Sort is an efficient, in-place sorting algorithm that works in average O(nlog(n)) time complexity. This approach involves selecting a 'pivot' element from the array and partitioning the remaining elements into two subarrays according to whether they are less than or greater than the pivot. The subarrays are then sorted recursively.
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
def partition(arr, low, high):
pivot = arr[low]
i = low - 1
j = high + 1
while True:
while True:
i += 1
if arr[i] >= pivot:
break
while True:
j -= 1
if arr[j] <= pivot:
break
if i >= j:
return j
swap(arr, i, j)
def quick_sort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi)
quick_sort(arr, pi + 1, high)
nums = [5, 2, 3, 1]
quick_sort(nums, 0, len(nums) - 1)
print(nums)public class QuickSort {
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[low];
int i = low - 1;
int j = high + 1;
while (true) {
do {
i++;
} while (arr[i] < pivot);
do {
j--;
} while (arr[j] > pivot);
if (i >= j)
return j;
swap(arr, i, j);
}
}
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi);
quickSort(arr, pi + 1, high);
}
}
public static void main(String[] args) {
int[] nums = {5, 2, 3, 1};
quickSort(nums, 0, nums.length - 1);
for (int num : nums) {
System.out.print(num + " ");
}
}
}#include <iostream>
#include <vector>
using namespace std;
void swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}
int partition(vector<int>& arr, int low, int high) {
int pivot = arr[low];
int i = low - 1, j = high + 1;
while (true) {
do {
i++;
} while (arr[i] < pivot);
do {
j--;
} while (arr[j] > pivot);
if (i >= j)
return j;
swap(arr[i], arr[j]);
}
}
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi);
quickSort(arr, pi + 1, high);
}
}
int main() {
vector<int> nums = {5, 2, 3, 1};
quickSort(nums, 0, nums.size() - 1);
for (int num : nums)
cout << num << ' ';
return 0;
}function swap(arr, i, j) {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
function partition(arr, low, high) {
let pivot = arr[low];
let i = low - 1;
let j = high + 1;
while (true) {
do { i++; } while (arr[i] < pivot);
do { j--; } while (arr[j] > pivot);
if (i >= j) return j;
swap(arr, i, j);
}
}
function quickSort(arr, low, high) {
if (low < high) {
let pi = partition(arr, low, high);
quickSort(arr, low, pi);
quickSort(arr, pi + 1, high);
}
}
let nums = [5, 2, 3, 1];
quickSort(nums, 0, nums.length - 1);
console.log(nums);#include <stdio.h>
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int low, int high) {
int pivot = arr[low];
int i = low - 1, j = high + 1;
while (1) {
do {
i++;
} while (arr[i] < pivot);
do {
j--;
} while (arr[j] > pivot);
if (i >= j)
return j;
swap(&arr[i], &arr[j]);
}
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi);
quickSort(arr, pi + 1, high);
}
}
int main() {
int nums[] = {5, 2, 3, 1};
int length = sizeof(nums) / sizeof(nums[0]);
quickSort(nums, 0, length - 1);
for (int i = 0; i < length; i++)
printf("%d ", nums[i]);
return 0;
}using System;
class QuickSort {
static void Swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
static int Partition(int[] array, int low, int high) {
int pivot = array[low];
int i = low - 1;
int j = high + 1;
while (true) {
do { i++; } while (array[i] < pivot);
do { j--; } while (array[j] > pivot);
if (i >= j) return j;
Swap(array, i, j);
}
}
static void QuickSortRec(int[] array, int low, int high) {
if (low < high) {
int pi = Partition(array, low, high);
QuickSortRec(array, low, pi);
QuickSortRec(array, pi + 1, high);
}
}
static void Main() {
int[] nums = {5, 2, 3, 1};
QuickSortRec(nums, 0, nums.Length - 1);
Console.WriteLine(string.Join(" ", nums));
}
}Python's quick sort uses in-place operations to reorder array elements around a pivot, chosen as the current low index. This decreases memory usage while maintaining efficient sorting.
Time Complexity: O(n2) in the worst case, O(nlog(n)) on average.
Space Complexity: O(log(n)).
Approach 3: Default Approach
function sortArray(nums: number[]): number[] {
function quickSort(l: number, r: number) {
if (l >= r) {
return;
}
let i = l - 1;
let j = r + 1;
const x = nums[(l + r) >> 1];
while (i < j) {
while (nums[++i] < x);
while (nums[--j] > x);
if (i < j) {
[nums[i], nums[j]] = [nums[j], nums[i]];
}
}
quickSort(l, j);
quickSort(j + 1, r);
}
const n = nums.length;
quickSort(0, n - 1);
return nums;
}func sortArray(nums []int) []int {
quickSort(nums, 0, len(nums)-1)
return nums
}
func quickSort(nums []int, l, r int) {
if l >= r {
return
}
i, j := l-1, r+1
x := nums[(l+r)>>1]
for i < j {
for {
i++
if nums[i] >= x {
break
}
}
for {
j--
if nums[j] <= x {
break
}
}
if i < j {
nums[i], nums[j] = nums[j], nums[i]
}
}
quickSort(nums, l, j)
quickSort(nums, j+1, r)
}class Solution {
fun sortArray(nums: IntArray): IntArray {
fun quickSort(left: Int, right: Int) {
if (left >= right) {
return
}
var i = left - 1
var j = right + 1
val pivot = nums[left]
while (i < j) {
while (nums[++i] < pivot) ;
while (nums[--j] > pivot) ;
if (i < j) {
val temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
}
}
quickSort(left, j)
quickSort(j + 1, right)
}
quickSort(0, nums.size - 1)
return nums
}
}impl Solution {
pub fn sort_array(mut nums: Vec<i32>) -> Vec<i32> {
let n = nums.len();
Self::quick_sort(&mut nums, 0, n - 1);
return nums;
}
fn quick_sort(nums: &mut Vec<i32>, left: usize, right: usize) {
if left >= right {
return;
}
let mut i = left as i32 - 1;
let mut j = right as i32 + 1;
let pivot = nums[left];
while i < j {
loop {
i += 1;
if nums[i as usize] >= pivot {
break;
}
}
loop {
j -= 1;
if nums[j as usize] <= pivot {
break;
}
}
if i < j {
nums.swap(i as usize, j as usize);
}
}
Self::quick_sort(nums, left, j as usize);
Self::quick_sort(nums, j as usize + 1, right);
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Merge Sort | Time Complexity: O(nlog(n)) |
| Quick Sort (Hoare's Partition Scheme) | Time Complexity: O(n2) in the worst case, O(nlog(n)) on average. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Merge Sort | O(n log n) | O(n) | When predictable performance and stable sorting are required |
| Quick Sort (Hoare Partition) | Average O(n log n), Worst O(n^2) | O(log n) | General case when in-place sorting and low memory usage are preferred |
| Counting Sort | O(n + k) | O(k) | When integer values fall within a small known range |
| Radix Sort | O(d(n + k)) | O(n + k) | Large arrays of integers where digit-based sorting is efficient |
Frequently asked questions
Is Sort an Array easy or hard?
The problem is rated Medium because it requires implementing a full sorting algorithm rather than calling a built-in function. Understanding recursion, partitioning, or merging logic is necessary to achieve the optimal O(n log n) solution.
How to solve Sort an Array in O(n)?
Linear-time sorting is possible only when additional constraints exist. Counting Sort or Radix Sort can achieve O(n + k) time where k is the value range or digit base. These approaches avoid element comparisons and instead group numbers into buckets based on their values or digits.
Sort an Array Python or Java solution?
Typical implementations use Merge Sort or Quick Sort. Python, Java, C++, and C solutions follow the same logic: recursively split the array (Merge Sort) or partition around a pivot (Quick Sort) until the array becomes fully sorted.
What is the best approach for Sort an Array?
Merge Sort and Quick Sort are the most common approaches. Both achieve O(n log n) average time complexity and are standard interview implementations. Merge Sort guarantees O(n log n) time but uses O(n) extra memory, while Quick Sort is in-place with O(log n) stack space but has a worst case of O(n^2).
Is Sort an Array asked at Google/Amazon/Meta?
Sorting fundamentals frequently appear in interviews at companies like Amazon, Google, and Meta. While the exact problem may vary, candidates are often asked to implement Merge Sort or Quick Sort to demonstrate understanding of divide-and-conquer and algorithmic complexity.
What data structure is used in Sort an Array?
The primary data structure is the array itself. Merge Sort temporarily uses auxiliary arrays during merging, while Quick Sort rearranges elements in-place using pointer swaps during partitioning.
What is the time complexity of Sort an Array?
Efficient comparison-based sorting algorithms such as Merge Sort and Quick Sort run in O(n log n) time on average. Merge Sort guarantees O(n log n) in all cases, while Quick Sort has an average of O(n log n) and a worst case of O(n^2).