I was wondering whether Python's Timsort behaved any differently (time and space wise) when the sort key is something like key=lambda v: v == 0, since it restricts the number of possible keys to just 2. I wrote some code to give me a general idea if that would be the case, but I believe I must have done it wrong because I get similar results that appear linear regardless of using a key function or not. For space complexity, I think I am also misusing tracemalloc: def measure_size(arr): format_str = "Curr: {:,}B, Peak: {:,}B" key_func = lambda a: a == 0 tracemalloc.start() tracemalloc.reset_peak() # sorted(arr, key=key_func) # ~1,607,000 B # sorted(arr) # ~1,195,832 B # arr[:] # ~800,000 B # arr.copy() # ~800,000 B print(format_str.format(*tracemalloc.get_traced_memory())) tracemalloc.stop() arr = [random.randint(0, 100) for _ in range(100000)] measure_size(arr) Uncommenting each of those lines yields the corresponding amount of PEAK usage. Why would using the key function increase the memory used? Anyway, this question could be generalized to any similar stable sorting algorithm, as in how the number of distinct possible keys affects the Time/Space complexity. Continue reading...
