Hey there everybody,

in one of Andreas's more recent videos I saw him sort something with QuickSort while trying to maintain an existing ordering. I thought that maybe switching to a stable sorting algorithm could be beneficial in that case. So I looked into the AK module, but could only find Quicksort. That made me create this issue.

I've been looking into stable sorting algorithms for a bit now and it seems to me that there might be a few candidates. I'd gladly implement whatever is more suited if that would be of interest.

Here are two algorithms that I'd consider suited:

• TimSort JDK Implementation (TimSort specification)
• GrailSort Paper

From my understanding TimSort is considered the fastest stable sorting algorithm for "real world data" (e.g., partially sorted data). However, the algorithm has linear worst-case space complexity. That's why I also considered GrailSort which is a stable in-place (i.e., constant worst-case space complexity) sorting algorithm.

I'd be really happy to have a discussion about these algorithms or some other suggestions, as well as my plans to start an implementation.