Implement bubble sort to sort an integer array in ascending order. On each pass, walk left to right and compare every adjacent pair; if the left element is greater than the right element, swap them. After each complete pass, the largest remaining unsorted element has bubbled to the end. Repeat until a full pass completes without any swaps, at which point the array is sorted.
Return a new sorted array; do not mutate the input.
Input
arr: an array of integers (may be empty)
Output
A new array containing the same integers sorted in ascending order.
Examples
Example 1
Inputarr = [3, 1, 4, 1, 5, 9]
Output[1, 1, 3, 4, 5, 9]
Explanation: Adjacent swaps move the larger values rightward across multiple passes.
Example 2
Inputarr = [1, 2, 3, 4, 5]
Output[1, 2, 3, 4, 5]
Explanation: The first pass performs no swaps, so the algorithm terminates early.
Constraints
0 <= arr.length
Elements are integers.
The input array must not be mutated.
Use the bubble sort algorithm and stop early when a pass has no swaps.