Body Sort

Purpose

This sort can be very fast.

It has elements from a heap sort and also a merge sort but combined in a way that is uniquely useful

Please enjoy.

Overview

This can be thought of as being inspired by small pond animals eating decaying leaves. The sort uses a primitive "body" data structure that will consume the numbers and then will output them in as sorted of a list as it is able to. It will be followed by a much slower merge sort that will put the data into it's ideal order.

Structure

The numbers are first processed by the body and then by a consolidator.

The body uses a similar formula to what is used during a heap sort. The difference is that in this case the tree part of the structure only contains an address to the actual object the object itself is stored in a main array. When ever an item in removed all of the address's for that result have to be removed from the funnel as well.

Observed Results

Incomplete:

Ratio of the final prep of the data as compared to a normal sort.

Note that their is a stair step effect.

Conclusion

Incomplete:

Implementation

All the heavy lifting is actually done by the "inplace_merge" it just has a lot of overhead.

This was written by Karl Kendall

This is an implementation of a experimental Body sort

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.

#include <iostream>

#include <string>

#include <vector>

#include<algorithm>

using namespace std;

int main()

{

system("pause");

}

Last updated: 3/23/2024