+ introduced unit SortBase, which implements the foundation for pluggable
sorting algorithms. A default QuickSort implementation is provided by the
unit. Other units can be added, to provide other sorting algorithms (e.g.
HeapSort, MergeSort, IntroSort, etc.)
* TList and TFPList updated to use the current default sorting algorithm defined
in SortBase for their .Sort method.

+ added TList.Sort overload with a sorting algorithm parameter

* added PtrList to the names of the current sort algorithm callback functions and
types, to indicate they sort a list of pointers

+ added the TItemListSorter_NoContext and TItemListSorter_Context procedure
types to sortbase. No implementation for them yet. They will allow sorting
an array with elements of arbitrary size (e.g. array of records).

* the type of the ItemCount parameter changed from PtrUInt to SizeUInt

* the first parameter of QuickSort_PtrList_NoContext renamed ItemPtrs for
consistency with the other similar procedures

* the Compare parameter renamed Comparer for consistency

+ added and implemented QuickSort_ItemList_Context

* use the sortbase sorting algorithm in fgl as well

* fixed TFPList.Sort. Scary news: turns out we don't have any tests for
TFPList.Sort or TList.Sort... :(

* use Inc() and Dec() instead of v:=v+1

* hook TFPSList.QuickSort to also call the default sorting algorithm from sortbase

+ added sortbase as a dependency to unit fgl in the makefiles

+ added a sort algorithm interface that accepts a custom callback function for
exchanging two elements. This is required for TStringList.Sort (and is the
most generic form for a sort algorithm interface that I can think of).

build/install fixes for the new sortbase unit for amiga, atari, aros and morphos

* fixed bug in QuickSort_ItemList_CustomItemExchanger_Context and
QuickSort_ItemList_Context and which can cause wrong sort results, due to not
taking into account that the pivot can be moved by the swap operation

* use the sort algorithm from sortbase for TStringList

+ added test for the sortbase unit

+ added .Sort() overloads with a SortingAlgorithm parameter to TFPGList,
TFPGObjectList, TFPGInterfacedObjectList and TFPSMap

+ added unit SortAlgs to rtl-extra. It implements extra sorting algorithms
that can be used in place of the default QuickSort implementation from unit
SortBase. Currently, only HeapSort is implemented, but others will be added
in the future.

+ keep track of the pivot index in all quicksort implementations. No functional changes,
but will be used to prevent overlap in the divided subregions and also infinite loops
in case of an incorrect compare function.

* use a try..finally block to protect against memory leaks if the comparison
callback function raises an exception in QuickSort_ItemList_Context

* use a more robust QuickSort implementation, that is guaranteed to never loop
forever and never access index out of bounds elements from the array when
being passed an incorrect comparison function. The resulting sort order is
still undefined in this case, though.

* use SizeUInt instead of longint for the array indices in the quicksort
implementations. This:
1) allows sorting arrays with >4G elements on 64-bit systems
2) allows sorting arrays with up to 4G (>2G) elements on 32-bit systems
3) uses 16-bit instead of the less efficient 32-bit indices on 16-bit and
8-bit platforms

* partition elements equal to the pivot on both sides of the pivot, since that
leads to much better performance when sorting lots of repeating elements

+ added comment with information about QuickSort and its specific implementation in unit SortBase

+ added additional notes in the comments for HeapSort

* fixed quicksort comment about memory use - our implementation uses O(log n) stack, not O(n log n)

+ added randomized quicksort to unit sortalgs

Add sortbase unit to global units list, as it can be compiled for all CPUs

* select the middle element in the default quicksort implementation in a way
that doesn't generate arithmetic overflow for very large arrays

* some formatting changes to avoid very large lines in the source code

Fix compilation on targets without Random: add $ifdef FPC_HAS_FEATURE_RANDOM

+ added test for unit sortalgs, that tests the heapsort and randomized quicksort algorithms

+ added .Sort overloads, that specify an algorithm and use the sortbase defined
algorithms for sorting TList, TFPList and TStringList when FPC_TESTGENERICS is
defined as well. Unfortunately, I couldn't test it, because the RTL doesn't
compile with FPC_TESTGENERICS, due to errors, completely unrelated to the
sortbase changes.

+ implemented IntroSort (hybrid between QuickSort and HeapSort) in unit SortAlgs

* Allow context when sorting lists (patch from Ondrej Pokorny, bug ID 000035962)