Show problems as
Classic problem #148MediumLinked ListTwo PointersDivide and ConquerSortingMerge Sort

Sort List

Real-world version: Order the Sounding Chain
Tracked in this browser only
Read Sort List on LeetCode(opens in a new tab)

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

A survey launch drags a sounder across a harbour and punches every reading onto a paper tag. Each tag holds one reading, the deviation in centimetres between the measured bed and the charted bed, and each tag is stapled to the tag punched after it. The final tag is stapled to nothing, so the run of tags can only be read forwards from the first one.

Because the harness passes plain JSON, the run reaches you as the array soundings, listing the readings from the first tag punched through to the last. An empty array means the launch recorded nothing. Your answer comes back in the same shape: the readings of the reordered run, first tag first.

The hydrographer wants the run reordered so the readings climb from lowest to highest. Repeated readings all stay in the run, once for each tag that carries them.

Do the work the tags call for: hold the readings in stapled tags and put them in order by restapling, that is by changing which tag each tag points at. Do not tip the readings into an array and hand that to a library sort. Keep the number of comparisons within O(n log n), and beyond the tags themselves use only a fixed amount of extra room.

Examples

Example 1

Input
soundings = [9, -4, 12, -4, 0, 7]
Output
[-4, -4, 0, 7, 9, 12]

Every reading from the run appears once, and each is at least as large as the one before it. Both tags reading -4 are still there.

Example 2

Input
soundings = [6, -1]
Output
[-1, 6]

The two tags come back with the lower reading in front.

Example 3

Input
soundings = [-15, 3, -15, -15]
Output
[-15, -15, -15, 3]

The three tags reading -15 all sit ahead of the tag reading 3, and none of them is dropped.

Constraints

  • The number of tags in the run is in the range [0, 5 * 10^4].
  • -10^5 <= soundings[i] <= 10^5

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 order_the_sounding_chain(soundings: list[int]) -> list[int]:
Java
public int[] orderTheSoundingChain(int[] soundings)

More on the same topics