qsort comparisons - qsort algorithm comparative benchmarks

	Commit message (Collapse)	Author	Age	Files	Lines
*	Use binary search in merge	Bobby Bingham	2014-08-23	1	-4/+3
\|
*	Optimize rotate	Bobby Bingham	2014-08-18	2	-17/+15
\| \| \| \| \| \| \| \| \| \| \| \| \| \| \|	Previously, we used three rotations. This was simple, but was aggressively inlined by gcc at higher optimization levels, massively bloating the code. Now, we take the front of the array, which is to be rotated to the end, and using a series of swaps, move it progressively closer to the end. When we can no longer perform a swap of the required size because we're too close to the end, we view the remaining operation as a rotate to the right with a smaller shift size. We repeat as necessary. This generates somewhat smaller code than the three reverses, even at -Os. It also shows up to a 25% overall performance improvement for grailsort on some inputs.
*	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.
*	Delete portions of grailsort reference code we're not using	Bobby Bingham	2014-08-16	1	-136/+19
\| \| \| \| \| \|	There's a lot of code in here that works with an externally provided extra buffer, but because we're not testing with that, it unfairly skews the code size against this algorithm.
*	Remove duplicate declarations of MIN_SIZE and MAX_SIZE	Bobby Bingham	2014-08-03	1	-3/+0
\|
*	Add quicksort-killer testcase	Bobby Bingham	2014-08-03	1	-0/+31
\| \| \| \| \| \| \|	This doesn't generate an input sequence up-front, but rather generates it on the fly in response to the order in which the algorithm is comparing elements in such a way as to invoke quadratic runtime in most quicksort implementations.
*	Make global state explicit in testcase generators	Bobby Bingham	2014-08-03	5	-26/+23
\| \| \| \| \| \| \|	The quicksort-killer testcase will require more global state, unless we go to the effort of implementing qsort_r versions of all the sorting algorithms. Since we're not doing that, we'll simply make the global state explicit.
*	Rename generators to testcases	Bobby Bingham	2014-08-03	5	-110/+119
\| \| \| \| \| \|	This is in preparation for adding an implementation of the quicksort-killer test case, which requires a custom comparison function rather than just a custom imput-generation function.
*	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
\|
*	Optimize swap for larger swaps	Bobby Bingham	2014-07-31	1	-0/+14
\|
*	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.
*	Use linear search when distributing buffer	Bobby Bingham	2014-07-31	1	-4/+2
\|
*	Add reference grailsort implementation	Bobby Bingham	2014-07-31	3	-0/+516
\|
*	Factor out binary_search	Bobby Bingham	2014-07-17	2	-21/+26
\|
*	Vastly improve performance of distribute_buffer	Bobby Bingham	2014-07-06	1	-10/+11
\|
*	Move wikisort/grailsort common code to a shared header	Bobby Bingham	2014-07-06	4	-210/+123
\|
*	Add a generator for slightly noisy reverse order data	Bobby Bingham	2014-07-06	1	-9/+20
\|
*	Add an implementation of grailsort	Bobby Bingham	2014-07-06	3	-0/+194
\|
*	Add the C++ reference wikisort implementation	Bobby Bingham	2014-07-04	4	-8/+985
\|
*	Remove unnecessary safeguard in rotate	Bobby Bingham	2014-06-30	1	-1/+0
\|
*	Move penda info into a struct array	Bobby Bingham	2014-06-30	1	-24/+25
\|
*	Small cleanup	Bobby Bingham	2014-06-30	1	-5/+2
\|
*	Use an array structure to track the temp buffer	Bobby Bingham	2014-06-30	1	-12/+13
\|
*	Rename stract blockarray to more generic "array"	Bobby Bingham	2014-06-29	1	-15/+15
\|
*	Don't bother merging when there are no pending elements	Bobby Bingham	2014-06-29	1	-3/+6
\|
*	Don't roll a b block if it doesn't make sense to	Bobby Bingham	2014-06-29	1	-6/+2
\| \| \| \| \| \| \|	This added a pathological case where each iteration we'd roll a b block into place, just to have to do a giant rotate to move all the accumulated b blocks over to make room for the a block that should have been inserted next.
*	Add generator of mostly sorted data	Bobby Bingham	2014-06-29	1	-4/+20
\|
*	Build with -Os	Bobby Bingham	2014-06-29	1	-1/+1
\|
*	Run smaller test cases before larger	Bobby Bingham	2014-06-29	1	-2/+2
\|
*	Move assert_sorted helper somewhere more public	Bobby Bingham	2014-06-29	3	-10/+15
\|
*	Generate nicer numbers for debugging	Bobby Bingham	2014-06-29	1	-1/+14
\|
*	Add wikisort optimizations for some common cases	Bobby Bingham	2014-06-29	1	-0/+9
\|
*	Initial stab at wikisort	Bobby Bingham	2014-06-29	4	-1/+227
\|
*	Add freebsd's qsort	Bobby Bingham	2014-06-21	3	-0/+168
\|
*	validate that sorter succeeded in sorting the input	Bobby Bingham	2014-06-21	1	-0/+11
\|
*	Add glibc's sorts	Bobby Bingham	2014-06-21	6	-4/+566
\| \| \| \|	Also rename musl's sort function for more consistency.
*	Initial commit: benchmark musl's qsort	Bobby Bingham	2014-06-20	7	-0/+369