# The Manual Sorter

> No shortcuts, no built-ins, just work.

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

Domain: Python · Difficulty: easy · Seniority: L4

## Problem

Given a list of integers, return it sorted ascending. Do NOT use sorted() or list.sort(). Implement any comparison-based sort yourself.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests whether a candidate can implement a **comparison-based sorting algorithm from scratch**. It probes understanding of algorithmic fundamentals and loop invariants, not just knowledge of Python built-ins.

---

### Break down the requirements

#### Step 1: Choose a simple sorting algorithm

Selection sort or insertion sort are easiest to implement correctly. Insertion sort is preferred because it runs in O(n) on nearly-sorted data.

#### Step 2: Maintain the sorted invariant

For insertion sort, elements to the left of the current position are always sorted. Each new element is shifted into its correct position.

#### Step 3: Return the sorted list

The sort happens in-place. Return the modified list.

---

### 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
```

> **Time and Space Complexity**
>
> **Time:** O(n^2) worst case when the list is reverse-sorted. O(n) best case when already sorted.
> 
> **Space:** O(1). The sort is in-place with only a constant number of extra variables.

> **Interviewers Watch For**
>
> Can you explain the loop invariant? At iteration i, elements `nums[0:i]` are sorted. This is the kind of reasoning interviewers value more than the code itself.

> **Common Pitfall**
>
> Off-by-one errors in the inner loop. The condition `j >= 0` must be checked before `nums[j] > key` to avoid an index out of bounds.

---

## Common follow-up questions

- Why not use merge sort or quicksort? _(Tests awareness of when simple O(n^2) algorithms are acceptable vs when O(n log n) is required.)_
- What is the best-case scenario for insertion sort? _(Tests understanding that nearly-sorted data makes insertion sort linear.)_
- How would you make this stable? _(Tests knowledge that insertion sort is already stable due to the strict `>` comparison.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_manual_sorter)
- [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). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.