python list.sort() vs. list.sort(key=itemgetter(0))

Question

I'm a python noob, but I'm using python to solve problems on leetcode. I solved one on leetcode (merge overlapping intervals). I have the following code:

    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) < 2: return intervals
        intervals.sort(key=itemgetter(0))
        merged = [intervals[0]]
        for interval in intervals[1:]:
            if merged[-1][1] >= interval[0]: merged[-1][1] = max(merged[-1][1],interval[1])
            else: merged.append(interval)
        return merged

I noticed that if I replace intervals.sort(key=itemgetter(0)) with intervals.sort() I get noticably worse performance (~80ms vs. ~110ms respectively)

Isn't sort() technically the same as sort(key=itemgetter(0))? Shouldn't they have identical runtime? Unless, is leetcode just being inconsistent with recoding the exact runtime?

Answer 1

intervals.sort(key=itemgetter(0)) is different from intervals.sort(). intervals.sort(key=itemgetter(0)) only compare the first items of two intervals, but intervals.sort() compare the second when the first are same. So intervals.sort(key=itemgetter(0)) may has more intervals look the same to sort, or just do less compare when compare intervals. It maybe one reason the first one run faster.

An other possible reason is optmization. Also Python is interpreted language, the interpreter may generate biniry code when running, and do some optmization. Which one will get better performance is dependent on the interpreter.

But empirically, in most online judges, the diffrence about 30ms is just measurement error. Try again you may get a different result.