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

Copyright (C) 2024  Karl Kendall

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