From f75d84cbdd2baa9633a5c20bdf8742425df8f19d Mon Sep 17 00:00:00 2001 From: Johannes Schickel Date: Fri, 30 Jul 2010 23:42:50 +0000 Subject: JANITORIAL: Some small explanation about stability of sorting algorithms. Special thanks to lskovlun for his suggestion to add this. svn-id: r51524 --- common/algorithm.h | 15 +++++++++++++-- 1 file changed, 13 insertions(+), 2 deletions(-) diff --git a/common/algorithm.h b/common/algorithm.h index 12c15f9b5d..9d22af4090 100644 --- a/common/algorithm.h +++ b/common/algorithm.h @@ -199,8 +199,19 @@ T sortPartition(T first, T last, T pivot, StrictWeakOrdering &comp) { * It compares data with the given comparator object comp. * * Like std::sort this is not guaranteed to be stable. - * Actually as the time of writing our implementation - * is unstable. + * + * Two small quotes from wikipedia about stability: + * + * Stable sorting algorithms maintain the relative order of records with + * equal keys. + * + * Unstable sorting algorithms may change the relative order of records with + * equal keys, but stable sorting algorithms never do so. + * + * For more information on that topic check out: + * http://en.wikipedia.org/wiki/Sorting_algorithm#Stability + * + * NOTE: Actually as the time of writing our implementation is unstable. */ template void sort(T first, T last, StrictWeakOrdering comp) { -- cgit v1.2.3