TypeError: '<' not supported between instances Python

So pre_sorted is a list with elements of [int, part]. When you sort this list and have two elements with the same integer value, it then compares the part values to try to determine which goes first. However, since you have no function for determining if a part is less than a part, it throws that error.

Try adding a function __lt__(self, other) to be able to order parts.

More on operators here

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.