Show problems as
Classic problem #912MediumArrayDivide and ConquerSortingHeap (Priority Queue)Merge SortBucket SortRadix SortCounting Sort

Sort an Array

Real-world version: Tool Offset Ordering
Tracked in this browser only
Read Sort an Array on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A machine shop fills in a card for every finishing pass it runs. Each card carries one signed offset in microns: negative when the pass left the part under the nominal size, positive when it left the part over.

You are given offsets, the figures in the order the cards were filed. Return the same figures rearranged from lowest to highest. Every card keeps its own entry, so a figure filed three times has to appear three times in what you return.

Arrange the figures yourself: do not call a library sorting routine or ordering helper. Your routine must run in O(n log n) time and use as little extra room as you can manage.

Examples

Example 1

Input
offsets = [12, -4, 12, 0, -4]
Output
[-4, -4, 0, 12, 12]

Both -4 cards and both 12 cards survive, so the answer holds five figures rising from -4 to 12.

Example 2

Input
offsets = [7, 3, 9, 1, 8, 2, 6]
Output
[1, 2, 3, 6, 7, 8, 9]

The seven figures are all different, so each one lands in its own place in the rising run.

Example 3

Input
offsets = [42]
Output
[42]

A single card is already in order on its own.

Constraints

  • 1 <= offsets.length <= 5 * 10^4
  • -5 * 10^4 <= offsets[i] <= 5 * 10^4

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def tool_offset_ordering(offsets: list[int]) -> list[int]:
Java
public int[] toolOffsetOrdering(int[] offsets)

More on the same topics