Sorting Simple sorts
146. Bubble Sort with Recursion
You are given an array of integers nums. Sort it in ascending order, smallest first, using bubble sort
written with recursion.
One pass of bubble sort walks along the array and compares each element with the one after it. When the left one is larger, the two swap. At the end of the pass, the largest value has reached the last position.
Write the sort as a recursive function. One call makes a single pass over the first n elements, then
calls itself to sort the first n − 1. The pass itself may be a loop; the recursion takes the place of
the loop that repeats the passes.
Change nums itself. The function returns nothing; the answer is what nums holds after it finishes.
Every copy of a repeated value stays. Do not call your language's built-in sort.
Example 1
Input: nums = [6, -1, 4, 2]
[-1,2,4,6]Explanation: The first call's pass carries 6 to the end, giving [-1, 4, 2, 6]. The call on the first three
carries 4 next to it: [-1, 2, 4, 6]. The calls on the first two and the first one change nothing.
Example 2
Input: nums = [0, -7, 3, -7, 0]
[-7,-7,0,0,3]Explanation: Negative values come before 0. Both −7s stay, side by side, and so do both 0s.
Example 3
Input: nums = [42]
[42]Explanation: One element is already sorted, so nothing moves.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 1000-109 ≤ nums[i] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.