Watch 10 video solutions for Sort an Array, a medium level problem involving Array, Divide and Conquer, Sorting. This walkthrough by NeetCodeIO has 72,427 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 * 104Problem 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 | 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 |