Short natural runs make merging slow, so TimSort grows every run to at least minRun items. Build the runs exactly as the TimSort page's template does:
start (strictly descending runs are reversed; otherwise the run is non-decreasing). Say it ends just before end.stop = Math.min(n, Math.max(end, start + minRun)). Insertion-sort the items from end to stop - 1 into the run, one at a time, each sliding left past strictly bigger items.nums[start..stop-1], and the next run starts at stop.Write buildRuns(nums, minRun) that returns the runs as sorted arrays, in order. Note that the items pulled into a run may themselves have been part of a natural run.
Input: nums = [1,4,7,9,8,6,3,2,5,10], minRun = 3 Output: [[1,4,7,9],[2,3,6,8],[5,10]]
Every natural run is already at least 3 long, except the last, which is cut short by the end of the list.
Input: nums = [6,2,9,4,8,1,7,3,5], minRun = 3 Output: [[2,6,9],[1,4,8],[3,5,7]]
6, 2 is a run of 2, grown with 9. 4, 8 is grown with 1. 7, 3 is grown with 5.
0 <= nums.length <= 100001 <= minRun <= 64-10^6 <= nums[i] <= 10^6Run 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 #212 TimSort Run Builder. 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.