Sweep Sort

Purpose

It uses 2n storage but preserves order and can be thought of as an alternative to Merge Sort

This sort is related to Quick Sort in that it uses a pivot.

One of pleasant parts of this sort is how it creates a soothing back and forth motion as it process the data.

Basic Design

The name is connected to how the sort operates

They are several versions of this sort. I will do my best to keep them separate.

The following debug messages may help explain the process the sort uses:

When a thread gets part of the task it will find an approximate pivot and then will split the work. As soon as some of the work can be given away, he will pass it on. When the work has followed the magnitude formula enough that it is all about the same size the thread will get to work sorting its section of the code.

It might be helpful to think of it like children trying to share bread. The first child will split the loaf and give about half if it away. Then he will split it again and give away the other half and so on until he has a piece about the same size as everyone else.

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

Observed Results

This data was created by running may different runs on the same computer.

The sort usually does not achieve hundred percent utilization.

Peaks in the graph represent when the program was doing multi-threading. The Valleys represent just standard single threaded operations.

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.