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 * 104The goal of #912 Sort an Array is to return the sorted version of a given integer array without relying on built-in sorting utilities. This problem is commonly used to test your understanding of classic sorting algorithms and their trade-offs.
A reliable approach is Merge Sort, a divide and conquer algorithm. The array is recursively split into smaller halves until each segment contains a single element. These segments are then merged in sorted order using a temporary structure. Merge Sort guarantees O(n log n) time complexity regardless of input distribution, making it a safe and predictable choice for interviews.
Another option is Heap Sort, which uses a priority queue (heap) to repeatedly extract the smallest element. It also runs in O(n log n) time and can be implemented with constant auxiliary space.
When the value range is limited, non-comparison techniques like Counting Sort or Radix Sort can achieve near O(n) performance. Choosing the right method depends on constraints such as array size and value range.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Merge Sort | O(n log n) | O(n) |
| Heap Sort | O(n log n) | O(1) |
| Counting Sort | O(n + k) | O(k) |
| Radix Sort | O(d × (n + k)) | O(n + k) |
Greg Hogg
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.
Time Complexity: O(nlog(n))
Space Complexity: O(n) (for temporary arrays used during merging)
1#include <stdio.h>
2
3void merge(int arr[], int left, int mid, int right) {
4 int n1 = mid - left + 1;
5 int n2 = right - mid;
6 int L[n1], R[n2];
7 for (int i = 0; i < n1; i++)
8 L[i] = arr[left + i];
9 for (int j = 0; j < n2; j++)
10 R[j] = arr[mid + 1 + j];
11 int i = 0, j = 0, k = left;
12 while (i < n1 && j < n2) {
13 if (L[i] <= R[j]) {
14 arr[k] = L[i];
15 i++;
16 } else {
17 arr[k] = R[j];
18 j++;
19 }
20 k++;
21 }
22 while (i < n1) {
23 arr[k] = L[i];
24 i++;
25 k++;
26 }
27 while (j < n2) {
28 arr[k] = R[j];
29 j++;
30 k++;
31 }
32}
33
34void mergeSort(int arr[], int left, int right) {
35 if (left < right) {
36 int mid = left + (right - left) / 2;
37 mergeSort(arr, left, mid);
38 mergeSort(arr, mid + 1, right);
39 merge(arr, left, mid, right);
40 }
41}
42
43int main() {
44 int nums[] = {5, 2, 3, 1};
45 int length = sizeof(nums) / sizeof(nums[0]);
46 mergeSort(nums, 0, length - 1);
47 for (int i = 0; i < length; i++)
48 printf("%d ", nums[i]);
49 return 0;
50}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.
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.
Time Complexity: O(n2) in the worst case, O(nlog(n)) on average.
Space Complexity: O(log(n)) for recursive stack space.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, sorting problems like this are frequently used in technical interviews at companies such as Google, Amazon, and Meta. They test understanding of fundamental algorithms like merge sort, heap sort, and counting-based techniques.
A common optimal approach is Merge Sort because it guarantees O(n log n) time complexity for all cases. It follows the divide-and-conquer strategy by splitting the array and merging sorted halves efficiently.
It depends on the chosen algorithm. Merge Sort relies on temporary arrays for merging, while Heap Sort uses a heap (priority queue) structure to repeatedly extract the smallest or largest element.
Counting Sort or Radix Sort works best when the integer range is limited or digits are processed individually. These non-comparison algorithms can outperform traditional sorts by achieving near linear time complexity under the right constraints.
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.