Consolidate functions for sorting vectors

[BenBE]

Currently there's Vector_quickSort, Vector_quickSortCustomCompare, and Vector_insertionSort for sorting vectors.

Apply the Highlander rule and let there only be one: Vector_sort.

While at it, update the signatures to allow for context support in the comparison functions:

typedef int (*Object_SortFn)(const void *a, const void *b, void *ctx);
int Vector_sort(Vector *v, Object_SortFn cmp, void *ctx);

Note: The single replacement API MUST be a stable sorting algorithm internally to conserve behaviour of Vector_insertionSort.

[Explorer09]

I think Vector_insertionSort algorithm has its merits and I oppose removing it for now. (1) Insertion sort is stable; (2) insertion sort works better for arrays that are 80% sorted.

[BenBE]

There's Timsort and it's derived version Powersort that are a combination of stable Merge sort with basically insertion sort for small sub-arrays.

So no, insertion sort won't be gone entirely, but it will be only a detail in the actual implementation using something more advanced. Thus, I'm fully aware that insertion sort and quick sort have their reason for existence in the current implementation, but it's for a reason, why several languages (Java, Python) switched to something else in their standard library when it comes to sorting.

[Explorer09]

@BenBE I was considering leaving two interfaces for sorting, like C++ std::sort and std::stable_sort, and omit the implementation details in the function names.

As for what algorithm will be for stable_sort, my idea was a kind of in-place merge sort that does not take O(n) extra memory (it would take at most O(log(n)) stack space for recursion, though).

[BenBE]

I'm currently looking into PowerSort, which is both stable AND a variant of merge sort. Also, it should be reasonable to implement its merging step in-place, leaving us with static worst case memory usage of O(log(n)).

[Explorer09]

I'm currently looking into PowerSort, which is both stable AND a variant of merge sort. Also, it should be reasonable to implement its merging step in-place, leaving us with static worst case memory usage of O(log(n)).

For me personally, any sorting algorithm that needs O(n) space would be out (including naïve merge sorts). It's simply a bad idea to require malloc'ing additional space to sort a big table. In-place merge sorts require slightly more time (O(n×log(n)×log(n)) in worst case) but the advantage of sorting in-place is what interested me. From what I've read on Wikipedia, the primary difference between Timsort and Powersort on the strategies of merging sub-arrays. That can be tuned easily after I try to write the primary in-place merge algorithm first (the in-place merge algorithm would be O(n×log(n)) per merge, comparing to O(n) which is the non-in-place version).

[BenBE]

I'm with you regarding memory usage of O(n), in particular with small arrays this introduces an overhead that's just going to cause performance issues due to how frequent we sort things.

My current WIP can be found at branch vector-sort-replace; but because I'm still working on the implementation of power sort it currently falls back to insertion sort for everything. That's really WIP; but will show the interface I'm aiming for.

NB: Currently looking through a lecture on Powersort (German) by one of the authors.

[zeneral]

Hi! I’m new here and looking to start contributing to open source. If I understand this issue correctly, there are several sorting algorithms mentioned, but the goal is to implement one reliable sorting method.

[Explorer09]

Just a reminder: I have an implementation ready for testing. #1798 It's a natural, in-place merge sort that works best with partially sorted data.