<< Introduction to algorithms >> ( Second Edition )
2.3-6 Insertion Sort with Binary Search
Observe that the while loop of line 5-7 of the Insertion Sort precedure in
Section 2.1 uses a linear search to scan ( backward ) through the sorted subarray
A[ 1 .. j - 1 ]. Can we use a binary search ( see Exercise 2.3-5 ) instead to improve
the overall worst-case running time of insertion sort to O( nlgn ) ?
Solution:
// 声明：本代码旨在实现原文的思想
// copyleft 2004 http://blog.csdn.net/mskia
// email: bitrain@hotmail.com
#ifndef Insertion_Sort_with_Binary_Search_by_mskia
#define Insertion_Sort_with_Binary_Search_by_mskia
namespace cc {
template< class T >
void insertion_sort_with_binary_search( T *first , T *last ) {
for ( T *i = first + 1; i <= last; ++i ) {
T *left = first , *right = i - 1;
while ( left <= right ) {
T *mid = left + ( ( right - left ) >> 1 );
if ( *i < *mid ) {
if ( *( mid - 1 ) < *i ) {
T bac = *i;
for ( T *p = i; p > mid; --p ) {
*p = *( p - 1 );
}
*mid = bac;
break;
} else {
right = mid - 1;
}
} else {
if ( *( mid + 1 ) > *i ) {
++mid;
T bac = *i;
for ( T *p = i; p > mid; --p ) {
*p = *( p - 1 );
}
*mid = bac;
break;
} else {
left = mid + 1;
}
}
}
}
return;
}
}
#endif