summaryrefslogtreecommitdiff
Commit message (Collapse)AuthorAgeFilesLines
* Add the system's qsort implementation to the comparisonBobby Bingham2014-08-311-0/+1
|
* Use binary search in distribute bufferBobby Bingham2014-08-231-5/+2
|
* Use binary search in mergeBobby Bingham2014-08-231-4/+3
|
* Optimize rotateBobby Bingham2014-08-182-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 grailsortBobby Bingham2014-08-161-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 usingBobby Bingham2014-08-161-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_SIZEBobby Bingham2014-08-031-3/+0
|
* Add quicksort-killer testcaseBobby Bingham2014-08-031-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 generatorsBobby Bingham2014-08-035-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 testcasesBobby Bingham2014-08-035-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 bnmelBobby Bingham2014-08-031-1/+1
|
* ReformatBobby Bingham2014-07-311-10/+3
|
* Remove grailsort dependency on bsearchBobby Bingham2014-07-311-3/+3
|
* Optimize swap for larger swapsBobby Bingham2014-07-311-0/+14
|
* Don't pre-sort the temp swap bufferBobby Bingham2014-07-311-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 orderBobby Bingham2014-07-311-6/+0
| | | | This increases code size, and doesn't seem to help very significantly.
* Use linear search when distributing bufferBobby Bingham2014-07-311-4/+2
|
* Add reference grailsort implementationBobby Bingham2014-07-313-0/+516
|
* Factor out binary_searchBobby Bingham2014-07-172-21/+26
|
* Vastly improve performance of distribute_bufferBobby Bingham2014-07-061-10/+11
|
* Move wikisort/grailsort common code to a shared headerBobby Bingham2014-07-064-210/+123
|
* Add a generator for slightly noisy reverse order dataBobby Bingham2014-07-061-9/+20
|
* Add an implementation of grailsortBobby Bingham2014-07-063-0/+194
|
* Add the C++ reference wikisort implementationBobby Bingham2014-07-044-8/+985
|
* Remove unnecessary safeguard in rotateBobby Bingham2014-06-301-1/+0
|
* Move penda info into a struct arrayBobby Bingham2014-06-301-24/+25
|
* Small cleanupBobby Bingham2014-06-301-5/+2
|
* Use an array structure to track the temp bufferBobby Bingham2014-06-301-12/+13
|
* Rename stract blockarray to more generic "array"Bobby Bingham2014-06-291-15/+15
|
* Don't bother merging when there are no pending elementsBobby Bingham2014-06-291-3/+6
|
* Don't roll a b block if it doesn't make sense toBobby Bingham2014-06-291-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 dataBobby Bingham2014-06-291-4/+20
|
* Build with -OsBobby Bingham2014-06-291-1/+1
|
* Run smaller test cases before largerBobby Bingham2014-06-291-2/+2
|
* Move assert_sorted helper somewhere more publicBobby Bingham2014-06-293-10/+15
|
* Generate nicer numbers for debuggingBobby Bingham2014-06-291-1/+14
|
* Add wikisort optimizations for some common casesBobby Bingham2014-06-291-0/+9
|
* Initial stab at wikisortBobby Bingham2014-06-294-1/+227
|
* Add freebsd's qsortBobby Bingham2014-06-213-0/+168
|
* validate that sorter succeeded in sorting the inputBobby Bingham2014-06-211-0/+11
|
* Add glibc's sortsBobby Bingham2014-06-216-4/+566
| | | | Also rename musl's sort function for more consistency.
* Initial commit: benchmark musl's qsortBobby Bingham2014-06-207-0/+369
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-15 05:53:51 +0000