# The Long Way Around

> Anyone can call the function. Order it by hand.

Canonical URL: <https://datadriven.io/problems/the_long_way_around>

Domain: Python · Difficulty: easy · Seniority: L4

## Problem

A batch job runs in a restricted runtime where the ordering built-ins are gone: no `sorted()`, no `list.sort()`, and no `min()` or `max()` to reach for. Given a list of integers `nums`, return them ordered smallest to largest.

## Worked solution and explanation

### What this really is

Strip the costume and this is 'can you order a list when every ordering built-in is taken away.' `sorted()`, `list.sort()`, `min()`, and `max()` are all off the table, so you cannot even lean on `min()` to pluck the next smallest each pass. The whole problem is the loop you would normally never have to write: walk the list, and for each new element slide it left past everything larger than it. Anyone can name insertion sort. The trick lives in the inner loop boundary: you have to test `j >= 0` BEFORE you touch `nums[j]`, or you walk off the front of the list. Get that order backwards and it is an IndexError on the first element that belongs at position zero.

---

### How to build it

#### Step 1: Pick the simplest sort you can defend

Insertion sort is the cleanest choice here: it is a handful of lines, sorts in place, and degrades gracefully. Selection sort works too, but with `min()` gone you would have to hand-scan for the smallest on every pass; insertion sort keeps the one comparison inline and finishes in a single pass over data that is already close to ordered.

#### Step 2: Hold the left side sorted

Everything to the left of the current index stays sorted at all times. Take the next element, remember it in `key`, and shift the sorted neighbors one slot to the right until you find the gap where `key` belongs. That invariant is the thing an interviewer actually wants to hear you say out loud.

#### Step 3: Land the element and return

Guard the inner loop with `j >= 0 and nums[j] > key`. Short-circuit evaluation means `j >= 0` is checked first, so you never index a negative-then-invalid position. Drop `key` into `nums[j + 1]` once the loop stops. The list is mutated in place, so return `nums`.

---

### The solution

**Insertion sort with in-place shifting**

```python
def manual_sort(nums):
    for i in range(1, len(nums)):
        key = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > key:
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = key
    return nums
```

> **Trick to solving**
>
> The order of the two conditions in `while j >= 0 and nums[j] > key` is load-bearing. Python evaluates left to right and stops at the first False, so `j >= 0` protects the `nums[j]` read. Flip them and the moment `key` is the new minimum you index `nums[-1]`, which quietly reads the wrong end of the list instead of failing loudly.

> **Performance insight**
>
> Time is O(n^2) in the worst case (a reverse-sorted list forces a full shift every step) and O(n) when the input is already ordered. Space is O(1): the sort happens in place with just `key` and `j` as scratch.

> **Interviewers watch for**
>
> State the invariant before you write a line: after iteration `i`, `nums[0:i+1]` is sorted. Candidates who narrate that reasoning read as senior; candidates who silently produce correct code but cannot explain why the inner loop terminates read as lucky.

> **Common pitfall**
>
> The failure everyone hits is the boundary check. Reading `nums[j]` before confirming `j >= 0`, or writing `key` back into `nums[j]` instead of `nums[j + 1]`, produces an off-by-one that either crashes on the smallest element or leaves one value stranded out of order.

---

## Common follow-up questions

- At what input size would you stop reaching for insertion sort and switch to merge sort or quicksort? _(Tests awareness of when an O(n^2) algorithm is acceptable versus when O(n log n) is required.)_
- What input makes this run in O(n), and why? _(Tests understanding that nearly-sorted data makes insertion sort linear.)_
- Is this sort stable as written, and what would break stability? _(Tests knowledge that the strict > comparison already preserves the order of equal elements.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_long_way_around)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.