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 * 104Merge 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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(nlog(n))
Space Complexity: O(n) (for temporary arrays used during merging)
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n2) in the worst case, O(nlog(n)) on average.
Space Complexity: O(log(n)) for recursive stack space.
| 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. |
This is the Most Asked FAANG Interview Question! - Two Sum - Leetcode 1 • Greg Hogg • 649,139 views views
Watch 9 more video solutions →Practice Sort an Array with our built-in code editor and test cases.
Practice on FleetCode