• Removing recursion

l := 1;

r ::= N;

initStack;

push( l );

push( r );

repeat

if r > l then {

i := partition( l , r );

if i- l > r-i then

push( l );

push( i - 1 );

l := i-1;

else

push( i + 1 );

push( r );

r := i - 1;

else

r := pop;

l := pop;

until Stack = 0

　

• Small subfile

if r - l <= 15 then insertion( l , r );

• Median-of-three

threeSort( a[l], a[(l+r)/2], a[r] );

swap( a[(l+r)/2], a[r-1] );

partition( l+1, r-2 );

　

										r-1↓
l↑				(l+r)/2↑							r↑

　

• No sentinel
• partition( l+1, r-2 )
• i≒(l+r)/2