Human-made Content Premium, Human-generated Content
Mergesort Investigation 4 - reuse linked lists

Mergesort Investigation 4 - reuse linked lists

Bruce Ediger

After I wrote a recursive merge sort, I reviewed it to ensure it wasn’t doing extra work. From that perspective, I noticed that for each of the 10 list sorts my benchmark program made for a given length linked list, it created a new linked list.

I thought that I could make the overall benchmark run faster by not creating a new, very large, linked list for every run, but rather re-using the existing list. I hoped to have the benchmark program use less time between the ten measured sort algorithm executions, not make the sorting faster. I surprised myself by getting the opposite effect.

Mergesort Investigation 3 - recursive implementation

Mergesort Investigation 3 - recursive implementation

Bruce Ediger

I wrote a traditional, top-down, recursive merge sort. The idea was to see if a different implementation exhibited the same dramatic, abrupt slowdowns. If the different implementation showed the same jumps in timings, the problem is with the operating system, the language run time, or the memory hardware. I know I said I’d ruled out the OS previously, but I was still suspicious.

Truck on a truck

Truck on a truck

Bruce Ediger

About May 30, 2024, I was driving on I-25, southbound, south of Loveland. I passed by a flatbed truck with a yellow, plastic dump truck strapped to the flatbed.

Star Wareos

Star Wareos

Bruce Ediger

Saw an exceptionally bad commercial tie-in the other days, Oreos, and Star Wars

Dobby: Bumper Stuck

Dobby: Bumper Stuck

Bruce Ediger

My pet Roomba, Dobby, got a thread wrapped around his constantly rotating whisk brush. Soon after that, a carpet loop got wrapped in there, too.