Split Quick Sort a Multi-Threaded Sort

• Download demo - 106.7 KB
• Download source - 2.6 KB

Introduction

This is an example of a sort that is multi threaded. Sorting can cause delays for the user. Most sorts are single threaded, but most computers have multiple cores that could help with the sort and remove the slowdown. This sort is intended to provide an example of how a sort can be multi-threaded and also faster than the original it is based on.

Using the Code

This code is primarily set up for timing and takes a vector or ints.

// Example of calling into the sort

//loading the vector with numbers
std::vector<int> arr;
for(int i = 0; i < 10000; i++)
{
     arr.push_back(temp);
}
// creating randomness in the vector
std::random_shuffle( arr.begin(), arr.end());

//Calling the sort:
splitQuick(arr);

Points of Interest

The statical part of this algorithm, the place were we pick the ideal pivot is very short.

We simply create a list of Candidates, we then sort the list and then select the one that is in the center to best approximate what we think the complete list will be.

std::vector<int> arr;
for(int i = 0; i < 10000; i++)
{
     arr.push_back(temp);
}

int selection = 513;
std::vector<int> candidates;

for(int j = 0; j < selection, j++)
{
     candidates.push_back( arr[ rand() % array.size() );
}
std::sort (candidates.begin(), candidates.end());
int pivot = candidates[candidates.size()/2];

This algorithm lets the worker threads recruit additional threads. It allows the work to be properly divided quickly. The "magnitude" variable tells the thread how many more times it can split.

//
total(int magnitude)
{
     while (magnitude > 0)
     {
          //split the work

          name = name << 1;
          int tempName = name | 1;
          magnitude--;

          //start new thread
          total(magnitude, tempName);
     }
     //perform own work
]
     std::cout << name << std::endl;
}

void splitQuick()
{
    total(3, 0);
}

int main()
{
    splitQuick();
}

/* output:

7
6
5
4
3
2
1
0

*/

Result

This sort does have extra overhead and does consume extra processing power, but gets the results faster by using the additional resources available.

History

• 24^th May, 2022: First draft complete