# The Forbidden Sorter

> Put the letters in order without the obvious tool.

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

Domain: Python · Difficulty: medium · Seniority: L3

## Problem

Given a list of single characters, return the list sorted in ascending alphabetical order. Do not use sort() or sorted(); implement your own sorting algorithm.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests whether a candidate can **implement a sorting algorithm from scratch**. It probes understanding of comparison-based sorting mechanics and the ability to translate algorithmic logic into working code.

---

### Break down the requirements

#### Step 1: Choose a sorting algorithm

Bubble sort, insertion sort, or selection sort are all appropriate for this problem since simplicity matters more than optimal performance.

#### Step 2: Compare characters using standard operators

Python characters compare by their Unicode code points, which gives alphabetical order for lowercase letters.

#### Step 3: Return the sorted list

The result should be a new list in alphabetical order.

---

### The solution

**Insertion sort for character ordering**

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

> **Time and Space Complexity**
>
> **Time:** O(n^2) worst case, O(n) best case (already sorted). Insertion sort is optimal for small or nearly-sorted inputs.
> 
> **Space:** O(n) for the copied list.

> **Interviewers Watch For**
>
> Which algorithm you choose and why. Insertion sort is a strong choice for interview settings because it is simple, stable, and performs well on small inputs.

> **Common Pitfall**
>
> Accidentally using Python's `sort()` or `sorted()` function. The problem explicitly forbids built-in sorting.

---

## Common follow-up questions

- What is the best-case time for insertion sort? _(Tests O(n) for already-sorted input, making it adaptive.)_
- How would you implement quicksort? _(Tests partition logic and recursion.)_
- Why is insertion sort preferred over bubble sort? _(Tests awareness that insertion sort has fewer swaps on average.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_forbidden_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.