Body Sort

This was the first sort I created on my own.

Background

This sort is designed to do as much processing as possible in a small working memory data area.

It then uses a "horse sort" to combine the working data sets.

Purpose

This algorithm is designed for cases where the working memory is limited and the external or regular memory is much slower.

It is also good for cases were the data is being added slowly or is not all ready at the same time.

Basic Design

This sort has some important similarities with the horse sort. One part is how it uses a very similar system of breaking the list down into horses that are runs from the bigger list. The merging the the list takes a surprising small amount of the overall time. Most of the time is from making the runs. In this case we use a modified priority queue to help us make the runs.

This sort uses a priority queue to make short "runs" of in-order sub-lists. The sublists are then combined latter.

The rules of the queue (At least in this case) are as follows.

The queue can have zero or more numbers. (it is not required to be full sized)

The queue has a relatively strict limit on size. Once that size has been reached it needs to start outputting numbers

When creating one of the runs it will consume as much of the unsorted list as possible to provide best chance to find the next number in the run.

Observed Result

This sort is based on pivot sort. We just allow multiple processors to help.

It works with several observations:

1. We can statistically gather a sample and then approximate what an ideal pivot would be.

2. The sooner we can get an additional core to help the better. We do not want only one core to act as the dispatcher.

3. The fewer Joins the better. We want each core to be able to complete it's work without interruption.

When a core gets the job of sorting a range in the array it will immediately verify it has permission to spit the work by looking to see if its magnitude is greater than zero and that the work is big enough to justify being split.

If it does have permission to split the work it will collect a sample and find an approximate middle pivot and then split the work into two sets. It will then give one of the sets to another thread along with all relevant information. If it still has permission to split the work further it will continue doing so.

When the work is done it will wait for all the threads it asked for help from to return and then return itself.

This sort has similar advantages to Quick Sort but is much faster on machines with multiple cores.

Notes on Implimintation and speed

// to replace later

Debuging information:

did split in 0: 0 524431 999999

made new thread 2

did split in 0: 0 258968 524431

made new thread 1

did split in 2: 524433 773525 999999

made new thread 3

doing quicksort in 2: 524433 773525

doing quicksort in 0: 0 258968

doing quicksort in 1: 258970 524431

doing quicksort in 3: 773527 999999

Conclusion

While experimental this multi threaded quick-sort was able to outperform it's single threaded comparison version.

Implementation

Sorting. This performs multithreaded quicksort

This program is free software; you can redistribute it and/or

modify it under the terms of the GNU General Public License

as published by the Free Software Foundation; either version 2

of the License.

This program is distributed in the hope that it will be useful,

but WITHOUT ANY WARRANTY; without even the implied warranty of

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

GNU General Public License for more details.

You should have received a copy of the GNU General Public License

along with this program; if not, write to the Free Software

Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.

5/11/2022