how to write Merge sort?

http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/CourseHome/index.htm 　マージソートを実装した。

namespace hito { namespace detail { template < typename Iterator > void merge_sort( Iterator first, Iterator last , typename std::iterator_traits<Iterator>::difference_type const n , typename std::iterator_traits<Iterator>::value_type * buf ) { if (n < 4) { for ( ; first != last ; ++first) { Iterator iter = std::min_element(first, last) ; if (iter != first) std::iter_swap(first, iter) ; } return ; } Iterator mid(first) ; std::advance(mid, n / 2) ; merge_sort(first, mid, n / 2, buf) ; merge_sort(mid, last, n / 2, buf) ; std::copy(first, mid, buf) ; typename std::iterator_traits<Iterator>::value_type * const end(buf + n / 2) ; while ( buf != end && mid != last ) { if ( *buf < *mid ) { *first = *buf ; ++buf ; } else { *first = *mid ; ++mid ; } ++first ; } std::copy(buf, end, first) ; } } // namespace detail template < typename Iterator > void merge_sort( Iterator first, Iterator last ) { typename std::iterator_traits<Iterator>::difference_type n = std::distance(first, last) ; if ( n == 1 ) return ; // Done typedef typename std::iterator_traits<Iterator>::value_type type ; type * buf = new type[(n + 1) / 2] ; detail::merge_sort(first, last, n, buf) ; delete[] buf ; } } // namespace hito

　結局、どう実装するのが一番最適なのだろう。これはBidirectinalIteratorでもソート可能だ。しかし、RandomAccessIteratorの場合は、引数のnなどいらない。ランダムアクセスイテレータに対して、std::distanceはフリーだからだ。実際どうするべきなんだろう。 　そしてふと、Nicolai JosuttisのSTL本を紐解くと、驚くべき事実が載っていた。stable_sortのイテレータはRandomAccessIteratorである。そんな馬鹿な。VC8のDinkumwareはBidirectionalIteratorでもソート可能だ。これは一体どういうことだ。規格を読むと、25.3.1.2に、確かにRandomAccessIteratorとある。しかし、実際にBidirectionalなlistのイテレータを渡しても、ソートできる（listはもっといいメンバ関数があるのだが）　ヘルプや、Dinkumwareのソースでは、双方向イテレータになっている。ふーむ。VCの独自仕様なのだろう。実際、マージソートは、双方向イテレータでも、それほど問題はないと思われる。