Why is a sorted list bigger than an unsorted list

Published on Author Ranjithilaga

This is due to Python allocating a bit more memory than required.

sorted creates a new list out of the sequence provided, sorts it in place and returns it. To create the new list, Python extends an empty sized list with the one passed; that results in the observed over-allocation (which happens after calling list_resize).

It is worth noting that this difference is mostly present when:

So, with a list-comp:

l = [i for i in range(10)]

getsizeof(l)          # 192
getsizeof(sorted(l))  # 200

Or a list literal:

l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

getsizeof(l)          # 144
getsizeof(sorted(l))  # 200

the sizes are slightly smaller.

When creating through list, the memory is always over-allocated; Python knows the sizes and preempts future modifications by over-allocating a bit based on the size:

l = list(range(10))

getsizeof(l)          # 200
getsizeof(sorted(l))  # 200

As a final note, it’s required to point out that this is behavior specific the C implementation of Python i.e an implementation detail. Jython, IronPython and any other implementation might/might not have the same behavior so don’t depend on it in any wacky way.

Comments

comments