I’ve benchmarked mergesort variants with randomly-chosen data values, initial data values already sorted, and initial data values sorted in descending order.
What happens to mergesort algorithms when initial data values are chosen for worst case time complexity?
There’s one more item I discovered during my mergesort investigation that bothers me. I wrote code that finishes with a low-to-high data value list. Starting with a “reverse sorted” (high-to-low data values) list with Wikipedia’s bottom up algorithm does not show the abrupt performance drops that a randomly-chosen data values initial list does, but has bumps in comparison count at lists of 2N+1 lengths.
Why is this?
.Data values, or arbitrarily changing .Next pointers
does not cause the performance drops.
I looked for other anomalies, too.
What happens if you compare the number of comparisons made by recursive and wikipedia bottom up algorithms if the initial list is pre-sorted (low data value to high data value) or reverse sorted (high data value to low).
My recursive mergesort algorithm, and the wikipedia bottom-up) algorithm read and write the same list nodes in the same order, for list lengths that are powers of two. Something other than mere data reading and pointer writing causes abrupt performance drops at linked list lengths of 2N+1 nodes.
I decided to count the number of comparisons used in merging lists. I had to write a different program so as to use an unsorted list with data in the same randomly chosen order for each of the three algorithms.
I tried several minor variations of recursive mergesort to try to understand the abrupt performance drops that my iterative mergesort code exhibits at some linked list lengths.
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.
I finally looked at the addresses of linked list nodes that my recursive and wikipedia bottom-up) algorithms read and write.
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.
As a way to see if merely accessing the linked list node’s memory causes the mergesort performance drops, I wrote two non-sorting functions and benchmarked them to try to distinguish
.Next pointers