Changeset 3119

Timestamp:

01/23/08 21:36:00 (10 months ago)

Author:

sean

Message:

Added an optimization to insertionSort, a part of the Tango sort routine. This refs #571

Files:

trunk/tango/core/Array.d

r3081	r3119
2016	2016	void insertionSort( size_t l, size_t r )
2017	2017	{
2018		for( size_t i = l; i <= r; ++i )
	2018	for( size_t i = r; i > l; --i )
	2019	{
	2020	// swap the min element to buf[0] to act as a sentinel
	2021	if( pred( buf[i], buf[i - 1] ) )
	2022	exch( i, i - 1 );
	2023	}
	2024	for( size_t i = l + 2; i <= r; ++i )
2019	2025	{
2020	2026	size_t j = i;
2021	2027	Elem v = buf[i];
2022	2028
2023		while( j != l && pred( v, buf[j - 1] ) )
	2029	// don't need to test (j != l) because of the sentinel
	2030	while( pred( v, buf[j - 1] ) )
2024	2031	{
2025	2032	buf[j] = buf[j - 1];