There is stable in-place merge sort, it runs in O(n*log(n)^2). It is about 3 times more complex than shell sort. I implemented it here https://github.com/thomasmueller/bau-lang/blob/main/src/test... (most sort algos you mentioned above are in the same direcory btw)

You didn't mention heap sort. A simple implementation, which doesn't do any method calls just like shell sort (also next to the merge sort above) is about twice as complex than shell sort.

▲

bxparks 5 hours ago | parent [-]

Thanks for the reference to in-place merge sort. GitHub is having a lot problems right now, I cannot see your code. I will look at it when I get a chance.

I think I ignored Heap sort because it uses O(N) extra RAM, which is precious on a resource-constrained microcontroller.

	▲	thomasmg an hour ago \| parent [-]
		Heap sort is in-place (and does not even need recursion, unlike quicksort). But yes, it is not stable, and usually slower than even shell sort (except for very large arrays).