Sort an Array - Solution & Explanation
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(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.
The C solution uses the merge sort algorithm, implementing both the merge and mergeSort functions. The array is recursively split into halves, sorted, and merged. Extra arrays L and R are used for the merge process, ensuring the correct elements are compared and copied back to the original array.
Complexity
Time Complexity: O(nlog(n))
Space Complexity: O(n) (for temporary arrays used during merging)
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.
The C solution for quick sort uses Hoare's partition scheme, where we move indices inward until elements that should be swapped are found. The quickSort function recursively applies this process.
Complexity
Time Complexity: O(n2) in the worst case, O(nlog(n)) on average.
Space Complexity: O(log(n)) for recursive stack space.
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
JavaScript
Rust
Kotlin
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 | — |
Detailed 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 |
Video Solution
Sort an Array - Leetcode 912 - Python • NeetCodeIO • 79,247 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Sort an Array easy or hard?
How to solve Sort an Array in O(n)?
Sort an Array Python or Java solution?
What is the best approach for Sort an Array?
Is Sort an Array asked at Google/Amazon/Meta?
What data structure is used in Sort an Array?
What is the time complexity of Sort an Array?
Ready to solve this problem?
Practice Sort an Array with our built-in code editor and test cases.
Practice on FleetCode