TypeError: ‘

Given that pre_sorted is a list of lists with items [fitness, part], this croaks whenever comparing two sublists with the same fitness.

Python lists sort lexicographically and are compared element-wise left to right until a mismatching element is found. In your case, the second element (part) is only accessed if the fitness of two parts is the same.

• [0, part0] < [1, part1] => does not compare part0 and part1 since the fitness is already different.
• [0, part0] < [0, part1] => does compare part0 and part1 since the fitness is the same.

Suggestion 1

Sort only by fitness: sorted(pre_sorted, key=operator.itemgetter(0))

Suggestion 2

Read the documentation for functools.total_ordering give part a total order:

@total_ordering
class part():
    [...]

    def __lt__(self, other):
        return self.number < other.number

And yeah, sorting lists of lists seems wrong. The inner elements might better be tuples, so you cannot accidentally modify the contents.