Du kannst ca. 10% sparen, indem Du die Rekursion rausnimmst.
Dazu implementierst du einen Stack, der die (L,R) Tupel verwaltet. Statt des rekursiven Aufrufes, schiebst du die untere und obere Grenze auf den Stack. Der Stack wird so lange abgearbeitet, bis er leer ist.
Dann kann es sein, das z.B. Insertionsort bei kleinen Abschnitten schneller ist.
Alles in Allem könntest Du so
imho max. 15% einsparen.
@Union: Ich wäre jede Wette eingegangen, das der Compiler das 'DIV 2' selber in 'SHR 1' optimiert. Bringt hier aber max 10ms.