Strategies for Stable Merge Sorting

Sam Buss, Alexander Knop

We introduce new stable natural merge sort algorithms, called $2$-merge sort and $\alpha$-merge sort. We prove upper and lower bounds for several merge sort algorithms, including Timsor…