Python self-referential list produces weird output on sorted

Question

I recently came across a weird discrepancy when trying to sort self-referential lists using .sort() and sorted(). I was hoping someone could shed some light on this. The code in question is the following:

lst = [1, 2, 3]

lst[0] = lst
lst[1] = lst
lst[2] = lst

print(lst)

print(sorted(lst))

lst.sort()

print(lst)

The above code produces the following output:

[[...], [...], [...]]
[[[...], [...], [...]], [[...], [...], [...]], [[...], [...], [...]]]
[[...], [...], [...]]

It's the output from print(sorted(lst)) that baffles me. Wonder if it is some form of recursion that's causing it?

sort and sorted don't really have anything to do with that. It's enough to compare the output of print(l) and print(list(l)) — DeepSpace
In other words, it is due to how new lists are constructed from an existing, self-reffering list, not to sorting — DeepSpace

Silvio Mayolo Silvio Mayolo · Accepted Answer · 2021-07-05T20:26:11

I'm going to call your list x, because frankly l looks too much like the number one and is throwing me off. So you've got a list x which looks like this

[x, x, x]

Now, we do

print(x)

Python is smart enough to say "hey, look, this list contains itself recursively, let's not print it again inside of itself." All of the places x appears in your list, we get [...]

[[...], [...], [...]]

Now consider

x.sort()
print(x)

We sort the list, which doesn't do much since every element is the same. However, crucially, it all happens in-place. The list started out looking like [x, x, x] and will end looking like [x, x, x], where x is our list. So the print looks the same.

[[...], [...], [...]]

Finally, your fun example.

sorted(x)

sorted, unlike list.sort, does not modify the list and instead produces a new list. Let's call this new list y. In your x.sort example, at the end, we have the same list x that looks like x = [x, x, x]. When we print the list, we immediately see the recursion and stop printing.

However, sorted(x) produces a new list. The list will still look like [x, x, x], but it's not the list x. It's a new list y = [x, x, x].

Now, we do

print(sorted(x))

Python sees a list of three elements: [x, x, x]. We look at each of those elements. We're printing y, so the fact that this list contains x is not a recursion problem; it's a perfectly ordinary list that contains other lists. So we print x inside of y. Now, one more layer down, we look inside x and see that it contains, lo and behold, x again. That is a recursion problem, but it happened one step later, because we made a new list that, although it looks identical to the original, is distinct.

[[[...], [...], [...]], [[...], [...], [...]], [[...], [...], [...]]]

Python self-referential list produces weird output on sorted

2 Answers