A sorting tutorial animates bottom-up merge sort. It starts with sorted blocks of width 1. In each pass, for start = 0, 2w, 4w, ..., it merges the block nums[start..start+w-1] with the block right after it, nums[start+w..start+2w-1] (either block may be cut short by the end of the list, and a block with no partner stays as it is). Then the width doubles. It stops once w reaches the list's length.
Write mergePasses(nums) that returns an array of snapshots: a copy of the list after each pass, in order. A list of 0 or 1 items needs no passes, so return [].
Input: nums = [5,2,4,7,1,3,2,6] Output: [[2,5,4,7,1,3,2,6],[2,4,5,7,1,2,3,6],[1,2,2,3,4,5,6,7]]
Width 1 sorts pairs, width 2 merges pairs into fours, width 4 merges the two halves.
Input: nums = [3,1,2] Output: [[1,3,2],[1,2,3]]
In the first pass, 2 has no partner and stays; the second pass merges [1, 3] with [2].
0 <= nums.length <= 64-1000 <= nums[i] <= 1000Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.
Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).
I'm here to help with #192 Bottom-Up Merge Passes. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.