As exercise to learn D2 ranges usage I've translated to D2 the C++ version of the Comb sort: http://en.wikipedia.org/wiki/Comb_sort#C.2B.2B_Implementation
It wasn't easy, but on those tests it works! Do you see errors or things that can be improved in this D2 code? I have verified that the program performs the same swaps with the array and the single linked list (but unittests are missing still). The combsort_impl inner function is a workaround for the lack of the "old" view of the input data in D postconditions. In C++ the gap is of type std::iterator_traits<ForwardIterator>::difference_type, but in D I have used just an int, I don't know why they have used that type in C++. In the C++ code itLeft and itRight are single items, probably single CPU words, while in D they can be two words or more (for example when data is a dynamic array). Can this cause some loss of performance compared to the C++ code? (I have not done benchmarks to compare the performance of the C++ version with the D version yet). import std.algorithm: swap, binaryFun, sort; import std.range: isForwardRange, walkLength, popFrontN, empty, front, popFront, hasSwappableElements, equal; import std.contracts: enforce; void combsort(alias less="a < b", Range)(Range data) if (isForwardRange!Range && hasSwappableElements!Range) { static void combsort_impl(Range data) { // From: http://en.wikipedia.org/wiki/Comb_sort enum double SHRINK_FACTOR = 1.247330950103979; int gap = walkLength(data); bool swapped = true; while ((gap > 1) || swapped) { if (gap > 1) gap /= SHRINK_FACTOR; swapped = false; auto right = data; popFrontN(right, gap); for (auto left = data; !right.empty; left.popFront, right.popFront) { if (binaryFun!(less)(right.front, left.front)) { swap(left.front, right.front); swapped = true; } } } } // postcondition verified in debug mode only. // Workaround: necessary because D postconditions don't // support the "old" (original input data view) yet. debug { auto data_copy = array(data); sort!(less)(data_copy); combsort_impl(data); enforce(equal(data, data_copy)); } else { combsort_impl(data); } } // end combsort() // no way to give a checked name to the unittest yet unittest { // tests of combsort() // TODO } // end tests of combsort() //--------------------- // imports local to the main() // function-local imports not supported yet import std.stdio: writeln; import std.range: SListRange, array; import std.algorithm: isSorted; void main() { int[] a = [10, 1, 5, 3, 7, -1, 5, 21, -3]; writeln(isSorted(a), " ", a); combsort(a); writeln(isSorted(a), " ", a); writeln(); auto lst = SListRange!int(10, 1, 5, 3, 7, -1, 5, 21, -3); writeln(isSorted(lst), " ", array(lst)); combsort(lst); writeln(isSorted(lst), " ", array(lst)); writeln(); /* // doesn't work with static arrays int[9] b = [10, 1, 5, 3, 7, -1, 5, 21, -3]; writeln(isSorted(b), " ", b); combsort(b); writeln(isSorted(b), " ", b); writeln(); */ } Bye, bearophile