Order the Ledger by Merging
EasySorting & SearchingFree
Problem
An accounting tool receives a day's ledger as an array of integer amounts amounts. The tool runs in an environment where the built-in sort is not available, so you must write the sort yourself.
Return a new array with the amounts in non-decreasing order. Your sort must run in O(n log n) time in the worst case, whatever the input looks like.
Example 1
- Input:
- amounts = [40, -5, 12, 0, 12]
- Output:
- [-5, 0, 12, 12, 40]
Split into [40, -5] and [12, 0, 12], sort each half, then merge the two sorted halves.
Example 2
- Input:
- amounts = [3]
- Output:
- [3]
Example 3
- Input:
- amounts = []
- Output:
- []
Constraints
- 0 ≤ amounts.length ≤ 10^5
- -10^9 ≤ amounts[i] ≤ 10^9
- Do not call the language's built-in sort.
Hint
Show the first hint
Sorting two halves separately is easier than sorting the whole thing. What would you do with two sorted halves?
Walkthrough
How to approach it
01Clarify before coding
- Should the input be modified or a new array returned? A new array; leaving the input untouched is fine either way.
- Are duplicates and negatives possible? Yes, both; equal amounts simply end up next to each other.
- Is O(n log n) needed in the worst case, or only on average? Worst case, which rules out a naive quick sort.
02Brute force
Insertion sort: grow a sorted prefix and slide each new amount left until it fits.
Cost: O(n²) time in the worst case (a reversed ledger), about 5·10^9 moves for n = 10^5. O(1) extra space.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.