Why does everyone love sorting algorithms?

I had an interview a few weeks ago, and was asked to implement a sorting algorithm. I didn’t manage to do it on the spot, but managed to revise and sent it back in my follow-up email. That was my second time implementing a sorting algorithm, the first was during my play through of Human Resource machine.

Captured from the recording of my play through

Unfortunately, my saves were not sync-ed properly to steam cloud, so I lost my solution to the puzzle. Essentially, I was implementing a bubble sort, I didn’t know until I went back to check out sorting algorithms. That was my first exposure to sorting algorithms, and I already had a decade of working experience.

Till this day, the interview was my second time implementing a sorting algorithm. Anyway, back to the puzzle, I am given 2 arrays:

list1 = [7, 3, 1, 5]
list2 = [2, 4, 8, 6]

Implement a function, that merges the two lists, and returns a sorted list, without calling .sort() or sorted(). Merging two lists together is easy, it is just:

from itertools import chain

def merge_then_sort(list1, list2):
    return chain(list1, list2)

Now that I have a merged list, time to sort them without the built-in sorting functions. Let’s start by looping through them:

from functools import reduce
from itertools import chain

def merge_then_sort(list1, list2):
    def inner(current, incoming):
        # append all incoming item for now
        current.append(incoming)
        return current

    return reduce(inner, chain(list1, list2), [])

I am aiming to just keep the list ordered from the beginning. My thought process is for every incoming item, I put it right after the item in the current list with the smallest positive difference.

def merge_then_sort(list1, list2):
    def inner(current, incoming):
        diff = [
            (idx, item - incoming)
            for idx, item in enumerate(current)
            if item - incoming > 0
        ]
        current.append(incoming)
        return current

    return reduce(inner, chain(list1, list2), [])

Let’s see what we should do next, considering we have this information (case A):

1. When we have current = [7], and incoming = 3
2. Then diff = [(0, 7 — 3 = 4)]
3. Find the minimum difference from diff (a number that is relatively just barely larger), and call it diff_min.
4. We should return current = [incoming, 7], by doing current.insert(diff_min[0], incoming)

What if we have something larger than everything in current (case B)?

1. When we have current = [3, 7] and incoming = 8
2. Then diff = []
3. We should return current = [3, 7, incoming], by appending to the list current.append(incoming)

Finding the minimum can be done with min, so we have this:

def merge_then_sort(list1, list2):
    def inner(current, incoming):
        if diff := [
            (idx, item, item - incoming)
            for idx, item in enumerate(current)
            if item - incoming > 0
        ]:
            # case A
            diff_min = min(diff, key=lambda item: item[-1])

            current.insert(diff_min[0], incoming)
        else:
            # case B
            current.append(incoming)

        return current

    return reduce(inner, chain(list1, list2), [])

We are done, now we see if we can clean this up better? The function min takes a default parameter according to the documentation. Let’s make it return the last index for current so we can reuse .insert() for case B.

from functools import reduce
from itertools import chain

def merge_then_sort(list1, list2):
    def inner(current, incoming):
        current.insert(
            # case A
            min(
                [
                    (idx, item - incoming)
                    for idx, item in enumerate(current)
                    if item - incoming > 0
                ],
                key=lambda item: item[-1],

                # case B
                default=(len(current), 0),
            )[0],
            incoming,
        )

        return current

    return reduce(inner, chain(list1, list2), [])

When I was talking to fellow engineers about the interview test, my former supervisor went to check my solution with qwen2.5-coder, and it suggested this solution:

def merge_then_sort(list1, list2):
    def inner(current, incoming):
        current.insert(
            # case A
            next(
                (idx for idx, item in enumerate(current) if item >= incoming),
                # case B
                len(current),
            ),
            incoming,
        )

        return current

    return reduce(inner, chain(list1, list2), []

It is essentially the same algorithm, but this eliminates the need for a call to min(). In a way it is clearer, but I am still quite happy with my own solution above, considering this is formerly my first time implementing the algorithm in a higher-level language. It is still a variation of bubble sort though, nothing too fancy here.

In the end, I failed the test, and did not proceed further in the job application. On the other hand, I still don’t understand the obsession of sorting algorithm, as I have not written anything close to this at work. Unfortunately, it seems like I would have to eventually re-do this for the third time, if I decide to complete Exapunks.

Anyway, that’s all for this week, I am slowly progressing through this year’s Advent of Code, hopefully I have something fun to share next week (assuming I am not giving up this year).