summaryrefslogtreecommitdiff
Commit message (Collapse)AuthorAgeFilesLines
* Optimize buffer stealing stepBobby Bingham2014-11-041-18/+16
| | | | | We can implement this with just a merge step, rather than completely resorting the b subsequence.
* Remove unused parameterBobby Bingham2014-11-041-2/+2
|
* Fill buffer with smallest elementsBobby Bingham2014-11-023-3/+36
| | | | | | 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 arrayBobby Bingham2014-11-021-37/+35
|
* Set output to unbuffered so results are visible soonerBobby Bingham2014-10-291-0/+2
|
* Perform swaps in larger chunks in merge stepBobby Bingham2014-10-291-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 assertionBobby Bingham2014-10-295-6/+10
|
* Add instrumentationBobby Bingham2014-10-2912-8/+99
| | | | | Track the number of comparisons, swaps, and rotations performed in each part of the sorting algorithm.
* Split helper functions into their own translation unitsBobby Bingham2014-10-267-92/+115
|
* Fix buffer distribution stepBobby Bingham2014-10-261-1/+1
| | | | If there are no sorted elements to distribute the buffer into, we're done.
* Rework block merge sort algorithmBobby Bingham2014-10-261-28/+36
| | | | | This was previously broken for certain inputs, particularly two concatenated sorted sequences.
* Fix grailsort block mergingBobby Bingham2014-09-011-28/+28
| | | | | Previously, we did not correctly handle some cases where a block contained elements with a uniform value.
* Add concatenated sorted arrays testcaseBobby Bingham2014-09-011-0/+8
|
* Add -lrt to buildBobby Bingham2014-09-011-1/+1
| | | | This is required on glibc versions before 2.17.
* Add changes missing from last commitBobby Bingham2014-09-011-1/+2
|
* Add musl's old heap sortBobby Bingham2014-09-013-2/+40
|
* 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
|
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-22 20:46:00 +0000