[libgee] Introduce TimSort and the public sorting API

[Didier 'Ptitjes' Villevalois <dvillevalois src gnome org>]

commit 183d3094c1f89346aaebafe4ebaaf6406fc354bd
Author: Didier 'Ptitjes <ptitjes free fr>
Date:   Wed Sep 9 22:25:00 2009 +0200

    Introduce TimSort and the public sorting API

 gee/Makefile.am           |    1 +
 gee/abstractlist.vala     |   10 +
 gee/arraylist.vala        |    4 +-
 gee/list.vala             |    7 +
 gee/readonlylist.vala     |    7 +
 gee/timsort.vala          |  712 +++++++++++++++++++++++++++++++++++++++++++++
 tests/testarraylist.vala  |   52 ++++
 tests/testlinkedlist.vala |   36 +++
 8 files changed, 827 insertions(+), 2 deletions(-)
---
diff --git a/gee/Makefile.am b/gee/Makefile.am
index 32567e4..d218923 100644
--- a/gee/Makefile.am
+++ b/gee/Makefile.am
@@ -35,6 +35,7 @@ libgee_la_VALASOURCES = \
 	readonlymap.vala \
 	readonlyset.vala \
 	set.vala \
+	timsort.vala \
 	treemap.vala \
 	treeset.vala \
 	$(NULL)
diff --git a/gee/abstractlist.vala b/gee/abstractlist.vala
index 3e06fd9..d122e15 100644
--- a/gee/abstractlist.vala
+++ b/gee/abstractlist.vala
@@ -84,4 +84,14 @@ public abstract class Gee.AbstractList<G> : Gee.AbstractCollection<G>, List<G> {
 			index++;
 		}
 	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public void sort (CompareFunc? compare = null) {
+		if (compare == null) {
+			compare = Functions.get_compare_func_for (typeof (G));
+		}
+		TimSort<G>.sort (this, compare);
+	}
 }
diff --git a/gee/arraylist.vala b/gee/arraylist.vala
index f99430e..f752ea9 100644
--- a/gee/arraylist.vala
+++ b/gee/arraylist.vala
@@ -48,8 +48,8 @@ public class Gee.ArrayList<G> : AbstractList<G> {
 	 */
 	public EqualFunc equal_func { private set; get; }
 
-	private G[] _items = new G[4];
-	private int _size;
+	internal G[] _items = new G[4];
+	internal int _size;
 
 	// concurrent modification protection
 	private int _stamp = 0;
diff --git a/gee/list.vala b/gee/list.vala
index 259ea80..7461905 100644
--- a/gee/list.vala
+++ b/gee/list.vala
@@ -96,5 +96,12 @@ public interface Gee.List<G> : Collection<G> {
 	 * @param collection collection of items to be inserted
 	 */
 	public abstract void insert_all (int index, Collection<G> collection);
+
+	/**
+	 * Sorts items by comparing with the specified compare function.
+	 *
+	 * @param compare_func compare function to use to compare items
+	 */
+	public abstract void sort (CompareFunc? compare_func = null);
 }
 
diff --git a/gee/readonlylist.vala b/gee/readonlylist.vala
index fd712d3..89fd8a6 100644
--- a/gee/readonlylist.vala
+++ b/gee/readonlylist.vala
@@ -105,5 +105,12 @@ public class Gee.ReadOnlyList<G> : Gee.ReadOnlyCollection<G>, List<G> {
 	public void insert_all (int index, Collection<G> collection) {
 		assert_not_reached ();
 	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public void sort (CompareFunc? compare = null) {
+		assert_not_reached ();
+	}
 }
 
diff --git a/gee/timsort.vala b/gee/timsort.vala
new file mode 100644
index 0000000..30971b4
--- /dev/null
+++ b/gee/timsort.vala
@@ -0,0 +1,712 @@
+/* timsort.vala
+ *
+ * Copyright (C) 2009  Didier Villevalois
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
+ *
+ * Author:
+ * 	Didier 'Ptitjes Villevalois <ptitjes free fr>
+ */
+
+/**
+ * A stable, adaptive, iterative mergesort that requires far fewer than n*lg(n)
+ * comparisons when running on partially sorted arrays, while offering
+ * performance comparable to a traditional mergesort when run on random arrays.
+ * Like all proper mergesorts, this sort is stable and runs O(n*log(n)) time
+ * (worst case). In the worst case, this sort requires temporary storage space
+ * for n/2 object references; in the best case, it requires only a small
+ * constant amount of space.
+ *
+ * This implementation was adapted from Tim Peters's list sort for Python,
+ * which is described in detail here:
+ *   [[http://svn.python.org/projects/python/trunk/Objects/listsort.txt]]
+ *
+ * Tim's C code may be found here:
+ *   [[http://svn.python.org/projects/python/trunk/Objects/listobject.c]]
+ *
+ * The underlying techniques are described in this paper (and may have even
+ * earlier origins):
+ *
+ *   "Optimistic Sorting and Information Theoretic Complexity"
+ *   Peter McIlroy
+ *   SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms), pp
+ *   467-474, Austin, Texas, 25-27 January 1993.
+ */
+internal class Gee.TimSort<G> {
+
+	public static void sort (List<G> list, CompareFunc compare) {
+		if (list is ArrayList) {
+			TimSort<G>.sort_arraylist ((ArrayList<G>) list, compare);
+		} else {
+			TimSort<G>.sort_list (list, compare);
+		}
+	}
+
+	private static void sort_list (List<G> list, CompareFunc compare) {
+		TimSort<G> helper = new TimSort<G> ();
+
+		helper.list_collection = list;
+		helper.array = list.to_array ();
+		helper.list = helper.array;
+		helper.index = 0;
+		helper.size = list.size;
+		helper.compare = compare;
+
+		helper.do_sort ();
+
+		// TODO Use a list iterator and use iter.set(item)
+		list.clear ();
+		foreach (G item in helper.array) {
+			list.add (item);
+		}
+	}
+
+	private static void sort_arraylist (ArrayList<G> list, CompareFunc compare) {
+		TimSort<G> helper = new TimSort<G> ();
+
+		helper.list_collection = list;
+		helper.list = list._items;
+		helper.index = 0;
+		helper.size = list._size;
+		helper.compare = compare;
+
+		helper.do_sort ();
+	}
+
+	private static const int MINIMUM_GALLOP = 7;
+
+	private List<G> list_collection;
+	private G[] array;
+	private unowned G[] list;
+	private int index;
+	private int size;
+	private Slice<G>*[] pending;
+	private int minimum_gallop;
+	private CompareFunc compare;
+
+	private void do_sort () {
+		if (size < 2) {
+			return;
+		}
+
+		pending = new Slice<G>[0];
+		minimum_gallop = MINIMUM_GALLOP;
+
+		Slice<G>* remaining = new Slice<G> (list, index, size);
+		int minimum_length = compute_minimum_run_length (remaining->length);
+
+		while (remaining->length > 0) {
+			// Get the next run
+			bool descending;
+			Slice<G>* run = compute_longest_run (remaining, out descending);
+#if DEBUG
+	message("New run (%d, %d) %s", run->index, run->length, descending ? "descending" : "ascending");
+#endif
+			if (descending) {
+				run->reverse ();
+			}
+
+			// Extend it to minimum_length, if needed
+			if (run->length < minimum_length) {
+				int sorted_count = run->length;
+				run->length = int.min (minimum_length, remaining->length);
+				insertion_sort (run, sorted_count);
+#if DEBUG
+	message("Extended to (%d, %d) and sorted from index %d", run->index, run->length, sorted_count);
+#endif
+			}
+
+			// Move remaining after run
+			remaining->shorten_start (run->length);
+
+			// Add run to pending runs and try to merge
+			pending += run;
+			merge_collapse ();
+		}
+
+		assert (remaining->index == size);
+
+		merge_force_collapse ();
+
+		assert (pending.length == 1);
+		assert (pending[0]->index == 0);
+		assert (pending[0]->length == size);
+
+		delete (remaining);
+		delete (pending[0]);
+	}
+
+	private delegate bool LowerFunc (G left, G right);
+
+	private inline bool lower_than (G left, G right) {
+		return compare (left, right) < 0;
+	}
+
+	private inline bool lower_than_or_equal_to (G left, G right) {
+		return compare (left, right) <= 0;
+	}
+
+	private int compute_minimum_run_length (int length) {
+		int run_length = 0;
+		while (length >= 64) {
+			run_length |= length & 1;
+			length >>= 1;
+		}
+		return length + run_length;
+	}
+
+	private Slice<G>* compute_longest_run (Slice<G>* a, out bool descending) {
+		int run_length;
+		if (a->length <= 1) {
+			run_length = a->length;
+			descending = false;
+		} else {
+			run_length = 2;
+			if (lower_than (a->list[a->index + 1], a->list[a->index])) {
+				descending = true;
+				for (int i = a->index + 2; i < a->index + a->length; i++) {
+					if (lower_than (a->list[i], a->list[i-1])) {
+						run_length++;
+					} else {
+						break;
+					}
+				}
+			} else {
+				descending = false;
+				for (int i = a->index + 2; i < a->index + a->length; i++) {
+					if (lower_than (a->list[i], a->list[i-1])) {
+						break;
+					} else {
+						run_length++;
+					}
+				}
+			}
+		}
+		return new Slice<G> (a->list, a->index, run_length);
+	}
+
+	private void insertion_sort (Slice<G>* a, int offset) {
+#if DEBUG
+	message("Sorting (%d, %d) at %d", a->index, a->length, offset);
+#endif
+		for (int start = a->index + offset; start < a->index + a->length; start++) {
+			int left = a->index;
+			int right = start;
+			G pivot = (owned) a->list[right];
+
+			while (left < right) {
+				int p = left + ((right - left) >> 1);
+				if (lower_than (pivot, a->list[p])) {
+					right = p;
+				} else {
+					left = p + 1;
+				}
+			}
+			assert (left == right);
+
+			a->list.move (left, left + 1, start - left);
+			a->list[left] = (owned) pivot;
+		}
+	}
+
+	private void merge_collapse () {
+#if DEBUG
+	message("Merge Collapse");
+#endif
+		int count = pending.length;
+		while (count > 1) {
+#if DEBUG
+	message("Pending count: %d", count);
+	if (count >= 3) {
+		message("pending[count-3]=%p; pending[count-2]=%p; pending[count-1]=%p", pending[count-3], pending[count-2], pending[count-1]);
+	}
+#endif
+			if (count >= 3 && pending[count-3]->length <= pending[count-2]->length + pending[count-1]->length) {
+				if (pending[count-3]->length < pending[count-1]->length) {
+					merge_at (count-3);
+				} else {
+					merge_at (count-2);
+				}
+			} else if (pending[count-2]->length <= pending[count-1]->length) {
+				merge_at (count-2);
+			} else {
+				break;
+			}
+			count = pending.length;
+#if DEBUG
+	message("New pending count: %d", count);
+#endif
+		}
+	}
+
+	private void merge_force_collapse () {
+#if DEBUG
+	message("Merge Force Collapse");
+#endif
+		int count = pending.length;
+#if DEBUG
+	message("Pending count: %d", count);
+#endif
+		while (count > 1) {
+			if (count >= 3 && pending[count-3]->length < pending[count-1]->length) {
+				merge_at (count-3);
+			} else {
+				merge_at (count-2);
+			}
+			count = pending.length;
+#if DEBUG
+	message("New pending count: %d", count);
+#endif
+		}
+	}
+
+	private void merge_at (int index) {
+#if DEBUG
+	message("Merge at %d", index);
+#endif
+		Slice<G>* a = pending[index];
+		Slice<G>* b = pending[index + 1];
+		try {
+			assert (a->length > 0);
+			assert (b->length > 0);
+			assert (a->index + a->length == b->index);
+
+			pending[index] = new Slice<G> (list, a->index, a->length + b->length);
+			pending.move (index + 2, index + 1, pending.length - index - 2);
+			pending.length -= 1;
+
+			int sorted_count = gallop_rightmost (b->peek_first (), a, 0); 
+			a->shorten_start (sorted_count);
+			if (a->length == 0) {
+				return;
+			}
+
+			b->length = gallop_leftmost(a->peek_last (), b, b->length - 1);
+			if (b->length == 0) {
+				return;
+			}
+
+			if (a->length <= b->length) {
+				merge_low (a, b);
+			} else {
+				merge_high (a, b);
+			}
+		} finally {
+			delete a;
+			delete b;
+		}
+	}
+
+	private int gallop_leftmost (G key, Slice<G>* a, int hint) {
+#if DEBUG
+	message("Galop leftmost in (%d, %d), hint=%d", a->index, a->length, hint);
+#endif
+		assert (0 <= hint);
+		assert (hint < a->length);
+
+		int p = a->index + hint;
+		int last_offset = 0;
+		int offset = 1;
+		if (lower_than (a->list[p], key)) {
+			int max_offset = a->length - hint;
+			while (offset < max_offset) {
+				if (lower_than (a->list[p + offset], key)) {
+					last_offset = offset;
+					offset <<= 1;
+					offset++;
+				} else {
+					break;
+				}
+			}
+
+			if (offset > max_offset) {
+				offset = max_offset;
+			}
+
+			last_offset = hint + last_offset;
+			offset = hint + offset;
+		} else {
+			int max_offset = hint + 1;
+			while (offset < max_offset) {
+				if (lower_than (a->list[p - offset], key)) {
+					break;
+				} else {
+					last_offset = offset;
+					offset <<= 1;
+					offset++;
+				}
+			}
+
+			if (offset > max_offset) {
+				offset = max_offset;
+			}
+
+			int temp_last_offset = last_offset;
+			int temp_offset = offset;
+			last_offset = hint - temp_offset;
+			offset = hint - temp_last_offset;
+		}
+
+		assert (-1 <= last_offset);
+		assert (last_offset < offset);
+		assert (offset <= a->length);
+
+		last_offset += 1;
+		while (last_offset < offset) {
+			int m = last_offset + ((offset - last_offset) >> 1);
+			if (lower_than (a->list[a->index + m], key)) {
+				last_offset = m + 1;
+			} else {
+				offset = m;
+			}
+		}
+
+		assert (last_offset == offset);
+		return offset;
+	}
+
+	private int gallop_rightmost (G key, Slice<G>* a, int hint) {
+#if DEBUG
+	message("Galop rightmost in (%d, %d), hint=%d", a->index, a->length, hint);
+#endif
+		assert (0 <= hint);
+		assert (hint < a->length);
+
+		int p = a->index + hint;
+		int last_offset = 0;
+		int offset = 1;
+		if (lower_than_or_equal_to (a->list[p], key)) {
+			int max_offset = a->length - hint;
+			while (offset < max_offset) {
+				if (lower_than_or_equal_to (a->list[p + offset], key)) {
+					last_offset = offset;
+					offset <<= 1;
+					offset++;
+				} else {
+					break;
+				}
+			}
+
+			if (offset > max_offset) {
+				offset = max_offset;
+			}
+
+			last_offset = hint + last_offset;
+			offset = hint + offset;
+		} else {
+			int max_offset = hint + 1;
+			while (offset < max_offset) {
+				if (lower_than_or_equal_to (a->list[p - offset], key)) {
+					break;
+				} else {
+					last_offset = offset;
+					offset <<= 1;
+					offset++;
+				}
+			}
+
+			if (offset > max_offset) {
+				offset = max_offset;
+			}
+
+			int temp_last_offset = last_offset;
+			int temp_offset = offset;
+			last_offset = hint - temp_offset;
+			offset = hint - temp_last_offset;
+		}
+
+		assert (-1 <= last_offset);
+		assert (last_offset < offset);
+		assert (offset <= a->length);
+
+		last_offset += 1;
+		while (last_offset < offset) {
+			int m = last_offset + ((offset - last_offset) >> 1);
+			if (lower_than_or_equal_to (a->list[a->index + m], key)) {
+				last_offset = m + 1;
+			} else {
+				offset = m;
+			}
+		}
+
+		assert (last_offset == offset);
+		return offset;
+	}
+
+	private void merge_low (Slice<G>* a, Slice<G>* b) {
+#if DEBUG
+	message("Merge low (%d, %d) (%d, %d)", a->index, a->length, b->index, b->length);
+#endif
+		assert (a->length > 0);
+		assert (b->length > 0);
+		assert (a->index + a->length == b->index);
+
+		int minimum_gallop = this.minimum_gallop;
+		int dest = a->index;
+		a->copy ();
+
+		try {
+			list[dest++] = b->pop_first ();
+			if (a->length == 1 || b->length == 0) {
+				return;
+			}
+
+			while (true) {
+				int a_count = 0;
+				int b_count = 0;
+
+				while (true) {
+					if (lower_than (b->peek_first (), a->peek_first ())) {
+						list[dest++] = b->pop_first ();
+						if (b->length == 0) {
+							return;
+						}
+
+						b_count++;
+						a_count = 0;
+						if (b_count >= minimum_gallop) {
+							break;
+						}
+					} else {
+						list[dest++] = a->pop_first ();
+						if (a->length == 1) {
+							return;
+						}
+
+						a_count++;
+						b_count = 0;
+						if (a_count >= minimum_gallop) {
+							break;
+						}
+					}
+				}
+
+				minimum_gallop++;
+
+				while (true) {
+					minimum_gallop -= (minimum_gallop > 1 ? 1 : 0);
+					this.minimum_gallop = minimum_gallop;
+
+					a_count = gallop_rightmost (b->peek_first (), a, 0);
+					a->merge_in (list, a->index, dest, a_count);
+					dest += a_count;
+					a->shorten_start (a_count);
+					if (a->length <= 1) {
+						return;
+					}
+
+					list[dest++] = b->pop_first ();
+					if (b->length == 0) {
+						return;
+					}
+
+					b_count = gallop_leftmost (a->peek_first (), b, 0);
+					b->merge_in (list, b->index, dest, b_count);
+					dest += b_count;
+					b->shorten_start (b_count);
+					if (b->length == 0) {
+						return;
+					}
+
+					list[dest++] = a->pop_first ();
+					if (a->length == 1) {
+						return;
+					}
+
+					if (a_count < MINIMUM_GALLOP && b_count < MINIMUM_GALLOP) {
+						break;
+					}
+				}
+
+				minimum_gallop++;
+				this.minimum_gallop = minimum_gallop;
+			}
+		} finally {
+			assert (a->length >= 0);
+			assert (b->length >= 0);
+			b->merge_in (list, b->index, dest, b->length);
+			a->merge_in (list, a->index, dest + b->length, a->length);
+		}
+	}
+
+	private void merge_high (Slice<G>* a, Slice<G>* b) {
+#if DEBUG
+	message("Merge high (%d, %d) (%d, %d)", a->index, a->length, b->index, b->length);
+#endif
+		assert (a->length > 0);
+		assert (b->length > 0);
+		assert (a->index + a->length == b->index);
+
+		int minimum_gallop = this.minimum_gallop;
+		int dest = b->index + b->length;
+		b->copy ();
+
+		try {
+			list[--dest] = a->pop_last ();
+			if (a->length == 0 || b->length == 1) {
+				return;
+			}
+
+			while (true) {
+				int a_count = 0;
+				int b_count = 0;
+
+				while (true) {
+					if (lower_than (b->peek_last (), a->peek_last ())) {
+						list[--dest] = a->pop_last ();
+						if (a->length == 0) {
+							return;
+						}
+
+						a_count++;
+						b_count = 0;
+						if (a_count >= minimum_gallop) {
+							break;
+						}
+					} else {
+						list[--dest] = b->pop_last ();
+						if (b->length == 1) {
+							return;
+						}
+
+						b_count++;
+						a_count = 0;
+						if (b_count >= minimum_gallop) {
+							break;
+						}
+					}
+				}
+
+				minimum_gallop++;
+
+				while (true) {
+					minimum_gallop -= (minimum_gallop > 1 ? 1 : 0);
+					this.minimum_gallop = minimum_gallop;
+
+					int k = gallop_rightmost (b->peek_last (), a, a->length - 1);
+					a_count = a->length - k;
+					a->merge_in_reversed (list, a->index + k, dest - a_count, a_count);
+					dest -= a_count;
+					a->shorten_end (a_count);
+					if (a->length == 0) {
+						return;
+					}
+
+					list[--dest] = b->pop_last ();
+					if (b->length == 1) {
+						return;
+					}
+
+					k = gallop_leftmost (a->peek_last (), b, b->length - 1);
+					b_count = b->length - k;
+					b->merge_in_reversed (list, b->index + k, dest - b_count, b_count);
+					dest -= b_count;
+					b->shorten_end (b_count);
+					if (b->length <= 1) {
+						return;
+					}
+
+					list[--dest] = a->pop_last ();
+					if (a->length == 0) {
+						return;
+					}
+
+					if (a_count < MINIMUM_GALLOP && b_count < MINIMUM_GALLOP) {
+						break;
+					}
+				}
+
+				minimum_gallop++;
+				this.minimum_gallop = minimum_gallop;
+			}
+		} finally {
+			assert (a->length >= 0);
+			assert (b->length >= 0);
+			a->merge_in_reversed (list, a->index, dest - a->length, a->length);
+			b->merge_in_reversed (list, b->index, dest - a->length - b->length, b->length);
+		}
+	}
+}
+
+[Compact]
+internal class Gee.Slice<G> {
+
+	public unowned G[] list;
+	public G[]? new_list;
+	public int index;
+	public int length;
+
+	public Slice (G[] list, int index, int length) {
+		this.list = list;
+		this.index = index;
+		this.length = length;
+	}
+
+	public void copy () {
+		new_list = new G[length];
+		Memory.copy (&new_list[0], &list[index], sizeof(G) * length);
+		list = new_list;
+		index = 0;
+	}
+
+	public inline void merge_in (G[] dest_array, int index, int dest_index, int count) {
+		Memory.move (&dest_array[dest_index], &list[index], sizeof(G) * count);
+	}
+
+	public inline void merge_in_reversed (G[] dest_array, int index, int dest_index, int count) {
+		Memory.move (&dest_array[dest_index], &list[index], sizeof(G) * count);
+	}
+
+	public inline void shorten_start (int n) {
+		index += n;
+		length -= n;
+	}
+
+	public inline void shorten_end (int n) {
+		length -= n;
+	}
+
+	public inline unowned G pop_first () {
+		length--;
+		return list[index++];
+	}
+
+	public inline unowned G pop_last () {
+		length--;
+		return list[index + length];
+	}
+
+	public inline unowned G peek_first () {
+		return list[index];
+	}
+
+	public inline unowned G peek_last () {
+		return list[index + length - 1];
+	}
+
+	public void reverse () {
+		int low = index;
+		int high = index + length - 1;
+		while (low < high) {
+			swap (low++, high--);
+		}
+	}
+
+	private inline void swap (int i, int j) {
+		G temp = (owned) list[i];
+		list[i] = (owned) list[j];
+		list[j] = (owned) temp;
+	}
+}
diff --git a/tests/testarraylist.vala b/tests/testarraylist.vala
index b298e1a..9a3a9f3 100644
--- a/tests/testarraylist.vala
+++ b/tests/testarraylist.vala
@@ -30,8 +30,12 @@ public class ArrayListTests : ListTests {
 	public ArrayListTests () {
 		base ("ArrayList");
 		add_test ("[ArrayList] selected functions", test_selected_functions);
+		add_test ("[ArrayList] small sort (insertion)", test_small_sort);
+		add_test ("[ArrayList] big sort (timsort)", test_big_sort);
 	}
 
+	private static const int BIG_SORT_SIZE = 1000000;
+
 	public override void set_up () {
 		test_collection = new ArrayList<string> ();
 	}
@@ -49,4 +53,52 @@ public class ArrayListTests : ListTests {
 		// Check the selected equal function
 		assert (test_list.equal_func == str_equal);
 	}
+
+	private void test_small_sort () {
+		var test_list = test_collection as ArrayList<string>;
+
+		// Check the collection exists
+		assert (test_list != null);
+
+		test_list.add ("one");
+		test_list.add ("two");
+		test_list.add ("three");
+		test_list.add ("four");
+		test_list.add ("five");
+		test_list.add ("six");
+		test_list.add ("seven");
+		test_list.add ("eight");
+		test_list.add ("nine");
+		test_list.add ("ten");
+		test_list.add ("eleven");
+		test_list.add ("twelve");
+
+		test_list.sort ();
+
+		assert (test_list.get (0) == "eight");
+		assert (test_list.get (1) == "eleven");
+		assert (test_list.get (2) == "five");
+		assert (test_list.get (3) == "four");
+		assert (test_list.get (4) == "nine");
+		assert (test_list.get (5) == "one");
+		assert (test_list.get (6) == "seven");
+		assert (test_list.get (7) == "six");
+		assert (test_list.get (8) == "ten");
+		assert (test_list.get (9) == "three");
+		assert (test_list.get (10) == "twelve");
+		assert (test_list.get (11) == "two");
+	}
+
+	private void test_big_sort () {
+		Gee.List<int32> big_test_list = new ArrayList<int32> ();
+		for (int i = 0; i < BIG_SORT_SIZE; i++) {
+			big_test_list.add (GLib.Random.int_range (1, BIG_SORT_SIZE - 1));
+		}
+
+		big_test_list.sort ();
+
+		for (int i = 1; i < BIG_SORT_SIZE; i++) {
+			assert (big_test_list[i - 1] <= big_test_list[i]);
+		}
+	}
 }
diff --git a/tests/testlinkedlist.vala b/tests/testlinkedlist.vala
index cc0a38a..d10c3be 100644
--- a/tests/testlinkedlist.vala
+++ b/tests/testlinkedlist.vala
@@ -29,6 +29,7 @@ public class LinkedListTests : ListTests {
 	public LinkedListTests () {
 		base ("LinkedList");
 		add_test ("[LinkedList] selected functions", test_selected_functions);
+		add_test ("[LinkedList] sort", test_sort);
 	}
 
 	public override void set_up () {
@@ -48,4 +49,39 @@ public class LinkedListTests : ListTests {
 		// Check the selected equal function
 		assert (test_list.equal_func == str_equal);
 	}
+
+	private void test_sort () {
+		var test_list = test_collection as LinkedList<string>;
+
+		// Check the collection exists
+		assert (test_list != null);
+
+		test_list.add ("one");
+		test_list.add ("two");
+		test_list.add ("three");
+		test_list.add ("four");
+		test_list.add ("five");
+		test_list.add ("six");
+		test_list.add ("seven");
+		test_list.add ("eight");
+		test_list.add ("nine");
+		test_list.add ("ten");
+		test_list.add ("eleven");
+		test_list.add ("twelve");
+
+		test_list.sort ();
+
+		assert (test_list.get (0) == "eight");
+		assert (test_list.get (1) == "eleven");
+		assert (test_list.get (2) == "five");
+		assert (test_list.get (3) == "four");
+		assert (test_list.get (4) == "nine");
+		assert (test_list.get (5) == "one");
+		assert (test_list.get (6) == "seven");
+		assert (test_list.get (7) == "six");
+		assert (test_list.get (8) == "ten");
+		assert (test_list.get (9) == "three");
+		assert (test_list.get (10) == "twelve");
+		assert (test_list.get (11) == "two");
+	}
 }