diff options
| author | Johannes Schickel | 2010-07-30 23:42:50 +0000 |
|---|---|---|
| committer | Johannes Schickel | 2010-07-30 23:42:50 +0000 |
| commit | f75d84cbdd2baa9633a5c20bdf8742425df8f19d (patch) | |
| tree | c8115e9e3ed4c6fcec0e8da35d7e7a3a1adbd56f | |
| parent | fd0f5696a53dd990ff23525ec6eb2576a61e4bfb (diff) | |
| download | scummvm-rg350-f75d84cbdd2baa9633a5c20bdf8742425df8f19d.tar.gz scummvm-rg350-f75d84cbdd2baa9633a5c20bdf8742425df8f19d.tar.bz2 scummvm-rg350-f75d84cbdd2baa9633a5c20bdf8742425df8f19d.zip | |
JANITORIAL: Some small explanation about stability of sorting algorithms.
Special thanks to lskovlun for his suggestion to add this.
svn-id: r51524
| -rw-r--r-- | common/algorithm.h | 15 |
1 files 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<typename T, class StrictWeakOrdering> void sort(T first, T last, StrictWeakOrdering comp) { |