64KB test

1MB test

8MB test

자 퍽이나 차이나지?

소스코드 :

// merge

static auto run( RESULT* dst, cuu size )

{

std::stable_sort( dst, dst + RESULT_SIZE );

}

// inplace_merge

template

static void imerge( Iter first, Iter last )

{

if( last <= first + 32 )

{

if ( last > first + 1 )

_Insertion_sort_unchecked( first, last, _Pass_fn(less<>()) );

return;

}

else

{

auto middle = first + ( last - first ) / 2;

imerge( first, middle );

imerge( middle, last );

std::inplace_merge( first, middle, last );

}

}

static auto run( RESULT* dst, cuu size )

{

imerge( dst, dst + RESULT_SIZE );

}

std::stable_sort 가 merge sort 인데, 내부적으로 32개 이하일땐 insertion_sort를 사용한다.

따라서 std::inlace_merge 쪽도 똑같이 해줌.

만약 insertion_sort 를 사용하지 않을 경우 양쪽다 1.9배 정도 더 소요된다.