Mergesort Investigation Summary
- Problem statement and some experimentation
- Explanation of the algorithm I came up with in 2021.
- Recursive merge sort algorithm to have something to compare
- Re-using linked lists while bench marking
- Effect of address-ordered linked lists
- Traversing linked lists does not exhibit weird performance drops at specific list lengths
- Effect of size of linked list nodes tests whether virtual memory is somehow involved. It is not.
- Bottom-up implementation with linked lists from Wikipedia, has the same performance drops as my July 2021 algorithm
- Memory access effects:
incrementing
.Data
values, or arbitrarily changing.Next
pointers does not cause the performance drops, and looking for other anomalies - Effect of garbage collection before preparing a new, unsorted, linked list
- The memory access patterns of recursive and wikipedia bottom up algorithms are identical. The performance is not.
- I wrote an iterative, explicit stack frame variation of recursive mergesort to try to get the same abrupt performance drops as the wikipedia bottom up algorithm. No joy.