computer science

Mergesort Investigation Summary

Mergesort Investigation Summary

Bruce Ediger
Mergesort Investigation 12 - simulate recursive algorithm with explicit call stack

Mergesort Investigation 12 - simulate recursive algorithm with explicit call stack

Bruce Ediger

I wrote variants of recursive mergesort that simulate function call recurision by iteration with an explicit stack of activation records. This is an effort to try to understand the abrupt performance drops that the wikipedia bottom up algorithm exhibits at some linked list lengths.

Incidentally, these two algorithms both satisfy the Daily Coding Problem problem statement. Their simulated call stack could potentially overflow for extremely long lists, but those stacks wouldn’t have to be much bigger to accomodate those long lists.

Mergesort Investigation 10 - garbage collection

Mergesort Investigation 10 - garbage collection

Bruce Ediger

Previously, in July 2021, I had tried to remove garbage collection from the possible variables affecting my iterative mergesort. I transliterated the Go code to a plain C version that could not have any garbage collection. The C code benchmarked very similarly to the Go code.

Mergesort Investigation 8 - bottom up

Mergesort Investigation 8 - bottom up

Bruce Ediger

I thought that since the purely recursive implementation of mergesort didn’t show weird, abrupt performance drops, traversing linked lists (no matter what order the nodes appeared in memory) also did not show abrupt performance drops, and that node size in memory caused different performance oddities, that the iterative implementation’s memory access patterns might be the cause.