Sorting Divide-and-conquer sorts
149. Quick Sort
You are given an array of integers nums. Sort it in ascending order, smallest first, using quick sort.
Quick sort picks one element, the pivot, and moves the values smaller than it to its left and the values larger than it to its right. Then it sorts the left part and the right part the same way.
Change nums itself. The function returns nothing; the answer is what nums holds after it finishes. Every
copy of a repeated value stays, so equal values end up next to each other.
The judge checks only the sorted array, so a call to your language's built-in sort would also be accepted. That skips the whole exercise, though. Write quick sort yourself.
Example 1
Input: nums = [5, -3, 8, 0, 5, 2]
[-3,0,2,5,5,8]Explanation: The smallest value, −3, comes first and the 8 comes last. Both 5s stay, side by side.
Example 2
Input: nums = [4, 4, 4, 4]
[4,4,4,4]Explanation: Every value is the same, so the array is already sorted.
Example 3
Input: nums = [6, 4, 2, 0, -2, -4]
[-4,-2,0,2,4,6]Explanation: The array comes sorted from largest to smallest, and it is turned around.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 105-109 ≤ nums[i] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.