Gnome Sort - C++ Implementation

C++ Implementation

This is a generic implementation mimicking the C++ Standard Library's sort function template. The deliberate limitation of BidirectionalIterator's operations to increment (++), decrement (--) and not equal (!=), is to ensure that the function template will work identically for: C arrays, C++11 arrays, deques, lists and vectors.

#include template void gnomeSort(BidirectionalIterator first, BidirectionalIterator last) { BidirectionalIterator i = first, j = first; ++j; while (j != last) if (*i <= *j) { ++i; ++j; } else { std::iter_swap(i, j); if (i != first) { --i; --j; } } }