Is `heapq.merge` stable?

Oh wow, mine’s slightly slower there? I wonder what the difference is. You’re using Windows, right? I sadly haven’t had a Windows machine in a long time.

About the randomization: If you run it a few times, do you get noticeably different times? More different than for multiple runs with a fixed seed? I don’t think the seed matters here. The data is large (one million values in each of the two iterables) and the algorithms are barely affected by data differences. They’re not like quicksort with a bad pivot selection, where different data can make a large difference in how good the pivots are, and make a significant difference in runtime that way.

Also, if I did use a fixed seed, I’d be measuring less random/general data. I’d be measuring for that particular seed. I don’t like that. I want different seeds. And I always run the whole script multiple times to see that I get “the same picture” every time.

Sometimes, when the algorithm is very much dependent on the data so that the seed really does matter, I use not just one random input but many. Maybe I should’ve done that for my isorted benchmark/graph somehow, because it included your quicksort. But I think I did get similar results in multiple runs, likely because your pivot selection is fairly robust. (Also, I was a bit sloppy with the benchmarking there because my main interest/point was the visualization.)

1 Like