Comment by kaba0

It may also be faster for small N, as the big O notation swallows the constant factor. It’s not accidental that standard lib’s sort algorithms will fall back to simple insertion sort at the end of recursion when n is small. (Though please correct me if I’m wrong, I’ve only once digged into the sort algorithm’s code in cpp and java’s std lib)