qsort comparisons - qsort algorithm comparative benchmarks

	Commit message (Collapse)	Author	Age	Files	Lines
*	Optimize buffer stealing step	Bobby Bingham	2014-11-04	1	-18/+16
\| \| \| \| \|	We can implement this with just a merge step, rather than completely resorting the b subsequence.
*	Remove unused parameter	Bobby Bingham	2014-11-04	1	-2/+2
\|
*	Fill buffer with smallest elements	Bobby Bingham	2014-11-02	1	-1/+33
\| \| \| \| \| \|	This avoids the need to distribute the buffer through the whole array at the end. It also allows us to skips most of the work for sorted and reverse-sorted inputs.
*	Switch to a stationary buffer, rather than moving it through the array	Bobby Bingham	2014-11-02	1	-37/+35
\|
*	Perform swaps in larger chunks in merge step	Bobby Bingham	2014-10-29	1	-11/+20
\| \| \| \| \| \|	Provides about a 10% overall speedup for the sorted+noise and reverse+noise test cases. Increases the number of comparisons in some of the other cases, but doesn't significantly change the runtime.
*	Add debugging assertion	Bobby Bingham	2014-10-29	1	-0/+4
\|
*	Add instrumentation	Bobby Bingham	2014-10-29	1	-0/+12
\| \| \| \| \|	Track the number of comparisons, swaps, and rotations performed in each part of the sorting algorithm.
*	Rework block merge sort algorithm	Bobby Bingham	2014-10-26	1	-28/+36
\| \| \| \| \|	This was previously broken for certain inputs, particularly two concatenated sorted sequences.
*	Fix grailsort block merging	Bobby Bingham	2014-09-01	1	-28/+28
\| \| \| \| \|	Previously, we did not correctly handle some cases where a block contained elements with a uniform value.
*	Use binary search in merge	Bobby Bingham	2014-08-23	1	-4/+3
\|
*	Slightly simplify grailsort	Bobby Bingham	2014-08-16	1	-7/+8
\| \| \| \| \|	Remove unused pending variable, and unused return value from merge(). Saves 29 bytes on x86_64.
*	Remove unnecessary test of bnmel	Bobby Bingham	2014-08-03	1	-1/+1
\|
*	Reformat	Bobby Bingham	2014-07-31	1	-10/+3
\|
*	Remove grailsort dependency on bsearch	Bobby Bingham	2014-07-31	1	-3/+3
\|
*	Don't pre-sort the temp swap buffer	Bobby Bingham	2014-07-31	1	-4/+5
\| \| \| \| \| \| \| \| \|	This is a close call. On the one hand, this buffer will get jumbled when used for merging adjacent blocks, so we'll need to sort it again before distributing it. On the other hand, by sorting it early, we know that we won't have to distribute it very far. In testing, pre-sorting seems to lose out overall.
*	Don't special-case reverse sort order	Bobby Bingham	2014-07-31	1	-6/+0
\| \| \| \|	This increases code size, and doesn't seem to help very significantly.
*	Move wikisort/grailsort common code to a shared header	Bobby Bingham	2014-07-06	1	-109/+8
\|
*	Add an implementation of grailsort	Bobby Bingham	2014-07-06	1	-0/+192