Welcome to Code Forum!

Join a community that supports you and your coding journey from day one. We strive to be a friendly, supportive community that empowers everyone to be better developers. By registering with us, you'll be able to discuss, share and private message with other members of our community.

SignUp Now!
  • Guest, before posting your code please take these rules into consideration:
    • It is required to use our BBCode feature to display your code. While within the editor click < / > or >_ and place your code within the BB Code prompt. This helps others with finding a solution by making it easier to read and easier to copy.
    • You can also use markdown to share your code. When using markdown your code will be automatically converted to BBCode. For help with markdown check out the markdown guide.
    • Don't share a wall of code. All we want is the problem area, the code related to your issue.

    GIF shows where to locate </> in the thread and or post editor toolbar.
    To learn more about how to use our BBCode feature, review our "How to post your code into threads" here.

    Thank you, Code Forum.

Parallel merge sort remainder X E.

JosiahMaybe

JosiahMaybe

Platinum Coder
I have a merge sort parallel on GPU, it works great for everything but that last remainder seemingly. It works by going from 1 to 1, doubling so 2 to 2... to last of that less than array size. The sorting algorithm is faster when sorting with 2 sorted things within themselves. For remainder such as 7 elements with 2 to 2, end 3, what math do you suggest for sorting? By last less than array size I mean like 4 to 4 with 7. I would like to avoid resorting as much as possible. Note that groups are sorted into each other, not as a whole until the end. I would prefer not to annex in more than a number to number thing so just remainder, it leaves one upon odd 1 to 1. That last thing to evenly distribute work.

GitHub - maybeJosiah/RinomXE: Open source 3 or more dimensional graphics math in Slang shaders. X E., this provides basic algorithm, the one ending with z. I can also confirm by other tests that all but remainder are sorting properly. AI was not of much help, I tried. X E.
 
Sort by date Sort by votes
I would not call this a merge sort.

It looks like an ordinary insertion sort, except you're using a binary search to find the insert position.

I'm surprised you're getting good results because merging two sorted blocks together in this way is not efficient.

I could be reading it wrong.
 
Upvote 0 Downvote
BlackCube said:
I would not call this a merge sort.

It looks like an ordinary insertion sort, except you're using a binary search to find the insert position.

I'm surprised you're getting good results because merging two sorted blocks together in this way is not efficient.

I could be reading it wrong.
Click to expand...
Well without order 1 million, with order, 10000, what would you suggest to be better without having shared memory or other things Slang does not support everywhere? As far as I can tell, merge sort was supposed to be somehow sort smaller chunks into bigger chunks until all sorted. Also, no atomics support on WGSL with this. X E.
 
Last edited:
Upvote 0 Downvote
Code: 
/*
7/22/2025, 6:03PM, start. X E.
7:32PM, like done untested. X E.
7:50PM, like done, untested. X E.
8:41PM, like done, untested. X E.
7/25/2025, 1:25PM, done better. X E.
7/29/2025, 1:46PM, start fixes for speed. X E.
2:08PM, break, broken. X E.
3:34PM, back.
7/30/2025, 11:56AM, ended 8:30PM yesterday, back today.
7:13PM, like done but could be more accurate. X E.
*/
/*
7/26/2023, 12:32PM, start.
Started by Norvel M. IV, Josiah.
Started on Ubuntu Touch using uText.
I define "X E" and "XE" ending things to mean:
"All that is near and with this me and since like my last adequate uncertainty to this me as per one might be input maybe or might not be input maybe or might be output maybe or might not be output maybe, maybe or maybe not, maybe.".
In a sentence, "A" may be lower case and if a period is after "X E" then period may be omitted from that definition.
This Rinom is intended to allow drawing in 3 or more dimensions using dimension axes on a 2 dimensional screen.
X E.
*/
// Define the input and output buffers
RWStructuredBuffer<float> points;
RWStructuredBuffer<float2> points2d;
RWStructuredBuffer<uint> shapes;
RWStructuredBuffer<uint> shapeEnds;
RWStructuredBuffer<float2> zDists;
RWStructuredBuffer<uint> drawOrder;
// Constant buffer for parameters
cbuffer ComputeParams {
    uint3 xyz;           // 3 integers for x, y, z
    uint unitSize;       // Number of floats per unit
    uint pointNumber;    // Number of points
    uint shapeNumber;    // Number of shapes
    float3 constants;   // 3 float constants
    float2 offset2d;    // 2d offsets
    uint shouldRound;   // Whether to round
    float roundWith;    // What to round with
    float precPad;      // Precision padding
    //X E
};
//X E
uniform uint step; // step is number to do to other number of it e.g. 2 to 2 or 1 to 1.
//X E

//Note that any more elements than half what a 32 bit number can hold may have bad behavior.
// Compute shader entry point
[shader("compute")]
[numthreads(256, 1, 1)] // Thread group size, adjustable
void mergeSortMain(uint3 dispatchThreadID : SV_DispatchThreadID) {
    //Exit early if index is out of bounds or buffer is 1 or less.
    if (dispatchThreadID.x*step*2+step/2 >= shapeNumber || shapeNumber == 0 || shapeNumber == 1) {
        //X E
        return;
        //X E
    }
    //Start merge sort
    uint4 indices = uint4(dispatchThreadID.x*step*2+step,dispatchThreadID.x*step*2,0,0);
    uint4 indices1 = uint4(0,0,dispatchThreadID.x*step*2+step*2,0);
    //Find end, shapeNumber or less.
    if (indices1[2]>shapeNumber) {
        if (step==1) {
            //X E
            return;
            //X E
        }
        if ((shapeNumber/step/2)%2==0) {
            indices[0]=dispatchThreadID.x*step*2+step/2;
            indices1[2]=dispatchThreadID.x*step*2+step;
            if (indices1[2]>shapeNumber) {
                indices1[2]=shapeNumber;
                indices1[3]=1;
            } else {
                indices1[3]=step/2;
            }
        } else {
            indices1[2]=shapeNumber;
        }
    }
    while (indices1[2] > indices[0]) {
        //Eliminate invalid data.
        if (zDists[drawOrder[indices[0]]][0] < -0.0&&indices1[3]==0) {
            //X E
            return;
            //X E
        } else {
            //Set up bounds. indices[1] is preset.
            indices[2]=indices[0]-1;
            //Loop and find where to input.
            while (indices[1]<indices[2]) {
                //Compare and eliminate all possibilities including current one. Round up.
                indices1[1]=(indices[1]+indices[2]+1)/2;
                indices1[0]=drawOrder[indices1[1]];
                if (zDists[drawOrder[indices[0]]][0]>zDists[indices1[0]][0]) {
                    indices[2]=indices1[1]-1;
                } else if (zDists[drawOrder[indices[0]]][0]<zDists[indices1[0]][0]) {
                    indices[1]=indices1[1]+1;
                } else if (zDists[drawOrder[indices[0]]][1]>zDists[indices1[0]][1]) {
                    indices[2]=indices1[1]-1;
                } else if (zDists[drawOrder[indices[0]]][1]<zDists[indices1[0]][1]) {
                    indices[1]=indices1[1]+1;
                } else {
                    //Equal numbers found, set to go after it.
                    indices[1]=indices1[1]+1;
                    break;
                }
            }
            if (indices[1]==indices[2]) {
                //Compare and find proper place.
                indices1[0]=drawOrder[indices[1]];
                if (zDists[drawOrder[indices[0]]][0]<zDists[indices1[0]][0]||(zDists[drawOrder[indices[0]]][0]==zDists[indices1[0]][0]&&zDists[drawOrder[indices[0]]][1]<zDists[indices1[0]][1])) {
                    indices[1]+=1;
                }
            }
            //Move all at or above found up one.
            if (indices[1]<indices[0]) {
                //Save a copy of the current index
                indices[3]=drawOrder[indices[0]];
                indices[2]=indices[0];
                //Shift.
                while (indices[1] != indices[2]) {
                    drawOrder[indices[2]]=drawOrder[indices[2]-1];
                    indices[2]-=1;
                }
                //Put index where it should be.
                drawOrder[indices[1]]=indices[3];
                indices[1]+=1;
            } else if (indices1[3]>0) {
                indices[1]=dispatchThreadID.x*step*2;
            } else if (indices1[3]==0) {
                //X E
                return;
                //X E
            }
        }
        //increment
        indices[0]+=1;
        //Push indices1[2] up if needed and reset indices[1].
        if (indices1[3] > 0&&indices1[2]<=indices[0]) {
            if ((shapeNumber/indices1[3]/2)%2==0) {
                indices1[3]/=2;
                indices1[2]+=indices1[3];
            } else {
                indices1[2]+=indices1[3];
            }
            if (indices1[2]>shapeNumber) {
                indices1[2]=shapeNumber;
                indices1[3]=1;
            }
            indices[1]=dispatchThreadID.x*step*2;
        }
    }
    //X E
}
//X E
Here is my current slightly buggy version, how to make it better?
 
Upvote 0 Downvote
Sorting by merging feels wrong because the final merge is equivalent to doing an insertion sort on half of the array, and only 1 thread is doing it.

If I could use parallel threads, and could not use extra memory, my first thought would be a quick search.

Partitioning is fast and simple.

If a block is small, use a standard sort, if a block is large, partition into 2 blocks then start another thread.

When all threads are done, there is no need to merge.
 
Upvote 0 Downvote
Well, Bitonic sort won't because it needs power of 2, quick sort is notoriously slow parallelized, Radix sort I do not know how to do, what else do you suggest? Maybe a Bitonic sort for next power of 2 down then merge in the rest? Bitonic handled a lot more, I think next is that. X E.
 
Upvote 0 Downvote
coda-sorting-benchmark/bitonic_sort.cu at main · hithuv/coda-sorting-benchmark, This works maybe but I will still need a swap for odd and not power of 2, I know my algorithm with 2 buffers is one copy in per element with two sorted things of any size. I think what I will do is benchmark them double buffered and have it like last one that was a whole thing to sort will be logged and next time last to be a whole thing next time and at the end merge in with my algorithm double buffered each segment pair based on that. From what I can tell mine uses a lot less threads. X E.
 
Upvote 0 Downvote
Play Snayk 3+, higher dimensional snake game?
I think I can find fault with that thing, may not handle equal numbers correct, so I am implementing my own. Also no license so no derivative works. I think I will do like a thread per element to sort and last remainders always increase size so I may do like first thread in an incomplete group, log it, then continue without it. If anyone wants to review before I start, duplicates are a major issue. My approach to handle them would be for one side (4 to 4, first or last) shift all to one side and other side shift all to other side, use existing counts of how much in that (example 4) and how much to determine a place per each. This should work with unequal sides e.g. 2 remainders. Double buffer to avoid data races. X E.
 
Upvote 0 Downvote
Code: 
/*
7/22/2025, 6:03PM, start. X E.
7:32PM, like done untested. X E.
7:50PM, like done, untested. X E.
8:41PM, like done, untested. X E.
7/25/2025, 1:25PM, done better. X E.
7/29/2025, 1:46PM, start fixes for speed. X E.
2:08PM, break, broken. X E.
3:34PM, back.
7/30/2025, 11:56AM, ended 8:30PM yesterday, back today.
7:13PM, like done but could be more accurate. X E.
8/5/2025, 2:29PM, begin revamp. X E.
2:45PM, begin tests. X E. 10:12PM, busted. X E.
8/6/2025, 2:24PM, Made Rust merge sort today, now implementing it here. X E.
2:30PM, like done, testing. X E.
5:24PM, returned to continue. X E.
*/
/*
7/26/2023, 12:32PM, start.
Started by Norvel M. IV, Josiah.
Started on Ubuntu Touch using uText.
I define "X E" and "XE" ending things to mean:
"All that is near and with this me and since like my last adequate uncertainty to this me as per one might be input maybe or might not be input maybe or might be output maybe or might not be output maybe, maybe or maybe not, maybe.".
In a sentence, "A" may be lower case and if a period is after "X E" then period may be omitted from that definition.
This Rinom is intended to allow drawing in 3 or more dimensions using dimension axes on a 2 dimensional screen.
X E.
*/
// Define the input and output buffers
RWStructuredBuffer<float> points;
RWStructuredBuffer<float2> points2d;
RWStructuredBuffer<uint> shapes;
RWStructuredBuffer<uint> shapeEnds;
RWStructuredBuffer<float2> zDists;
RWStructuredBuffer<uint> drawOrder;
// Constant buffer for parameters
cbuffer ComputeParams {
    uint3 xyz;           // 3 integers for x, y, z
    uint unitSize;       // Number of floats per unit
    uint pointNumber;    // Number of points
    uint shapeNumber;    // Number of shapes
    float3 constants;   // 3 float constants
    float2 offset2d;    // 2d offsets
    uint shouldRound;   // Whether to round
    float roundWith;    // What to round with
    float precPad;      // Precision padding
    //X E
};
//X E
uniform uint step; // step is number to do to other number of it e.g. 2 to 2 or 1 to 1.
//X E

//Note that any more elements than half what a 32 bit number can hold may have bad behavior.
// Compute shader entry point
[shader("compute")]
[numthreads(256, 1, 1)] // Thread group size, adjustable
void mergeSortMain(uint3 dispatchThreadID : SV_DispatchThreadID) {
    //Exit early if index is out of bounds or buffer is 1 or less.
    if (dispatchThreadID.x*step*2 >= shapeNumber || shapeNumber == 0 || shapeNumber == 1) {
        //X E
        return;
        //X E
    }
    //Start merge sort
    uint4 indices = uint4(dispatchThreadID.x*step*2+step,dispatchThreadID.x*step*2,0,0);
    uint4 indices1 = uint4(0,0,dispatchThreadID.x*step*2+step*2,0);
    //Find end, shapeNumber or less.
    if (indices1[2]>shapeNumber) {
        if (step==1) {
            //X E
            return;
            //X E
        }
        indices1[3]=dispatchThreadID.x*step*2;
        if (indices[0]<shapeNumber) {
            indices1[3]=indices[0];
        } else if (indices1[3]+step/2<shapeNumber) {
            indices1[3]+=step/2;
        } else {
            //X E
            return;
            //X E
        }
        if (indices[0]<indices1[3]) {
            indices1[2]=indices1[3];
            indices1[3]=1;
        } else {
            indices[0]=indices1[3];
            indices1[2]=shapeNumber;
            indices1[3]=0;
        }
    }
    while (indices1[2] != indices[0]) {
        //Set up bounds. indices[1] is preset.
        indices[2]=indices[0]-1;
        //indices[1]=id*step*2;
        //Loop and find where to input.
        while (indices[1]<indices[2]) {
            //Compare and eliminate all possibilities including current one. Round up.
            indices1[1]=(indices[1]+indices[2]+1)/2;
            indices1[0]=drawOrder[indices1[1]];
            if (zDists[drawOrder[indices[0]]][0]>zDists[indices1[0]][0]) {
                indices[2]=indices1[1]-1;
            } else if (zDists[drawOrder[indices[0]]][0]<zDists[indices1[0]][0]) {
                indices[1]=indices1[1]+1;
            } else if (zDists[drawOrder[indices[0]]][1]>zDists[indices1[0]][1]) {
                indices[2]=indices1[1]-1;
            } else if (zDists[drawOrder[indices[0]]][1]<zDists[indices1[0]][1]) {
                indices[1]=indices1[1]+1;
            } else {
                //Equal numbers found, set to go after it.
                indices[1]=indices1[1];
                break;
            }
        }
        if (indices[1]==indices[2]) {
            //Compare and find proper place.
            indices1[0]=drawOrder[indices[1]];
            if (zDists[drawOrder[indices[0]]][0]<zDists[indices1[0]][0]||(zDists[drawOrder[indices[0]]][0]==zDists[indices1[0]][0]&&zDists[drawOrder[indices[0]]][1]<zDists[indices1[0]][1])) {
                indices[1]+=1;
            }
        }
        //Move all at or above found up one.
        if (indices[1]<indices[0]) {
            //Save a copy of the current index
            indices[3]=drawOrder[indices[0]];
            indices[2]=indices[0];
            //Shift.
            while (indices[1] != indices[2]) {
                drawOrder[indices[2]]=drawOrder[indices[2]-1];
                indices[2]-=1;
            }
            //Put index where it should be.
            drawOrder[indices[1]]=indices[3];
            indices[1]+=1;
        } else if (indices1[3] != 0) {
            indices[0]=indices1[2]-1;
        } else {
            //X E
            return;
            //X E
        }
        //increment
        indices[0]+=1;
        if (indices1[3] != 0&&indices[0]==indices1[2]) {
            indices1[2]=shapeNumber;
            indices[1]=dispatchThreadID.x*step*2;
            indices1[3]=0;
        }
    }
    //X E
}
//X E
Here is the shader. X E.
 
Upvote 0 Downvote

New Threads

Latest posts

Share this page

Buy us a coffee!

Buy me a coffee.
Code Academy Advertisement
DataCamp Advertisement

About Us

Code Forum is a community platform where coding enthusiasts can connect with other developers, engage in discussions, ask for help, and share their knowledge with a supportive community. It's a perfect place to improve your coding skills and to find a community of like-minded individuals who share your passion for coding.

Site links

Stay Connected

Back
Top Bottom