Why is this merge sort not sorting equals correctly?

maybeJosiah · August 20, 2025, 6:48pm

mergeSortMain is all I need help with, when there are equal elements it fails to input all indices and it should have all indices, do you see anything wrong? fromStart is supposed to be from start of its half, the id. indices[0] is id storage, indices[1] is lower bound, indices[2] is upper bound. indices[3] is a flag for which half. aux[0] and aux[1] are just intermediary values. aux[2] is initial indices[1] and aux[3] is initial indices[2]. Run this in Rust playground.

//8/7/2025, 5:47PM, better version. X E.
//8/19/2025, 4:16PM, begin work on double buffered thread per element version. X E.
//8:26PM, break, broken same number stuff. X E.
//8/20/2025, 12:53PM, return. X E.
//2:05PM, break, still broken. X E.
use getrandom;
//use std::mem;
#[allow(warnings)]
fn random_range(start:i32,end:i32) -> i32 {
    let test = getrandom::u32();
    if !test.is_ok() {
        return start;
    }
    let test1 = test.unwrap();
    let mut test2 = start;
    let mut bit = 0;
    while (1<<bit) <= end-start {
        test2+=((((test1 >> bit) & 1) << bit) as i32);
        bit+=1;
    }
    if test2 > end {
        //X E
        return end;
        //X E
    } else if test2 < start {
        //X E
        return start;
        //X E
    } else {
        //X E
        return test2;
        //X E
    }
}
fn random() -> f32 {
    //X E
    return random_range(0,1) as f32;
    //X E
}
//X E
#[allow(warnings)]
fn mergeSortMain(id:usize,step:&Vec<usize>,shapeNumber:usize,zDists:&mut Vec<[f32; 2]>,drawOrder:&mut Vec<usize>,tempOrder:&mut Vec<usize>) {
    //Exit early if index is out of bounds or buffer is 1 or less.
    if (id >= shapeNumber || shapeNumber == 0 || shapeNumber == 1) {
        //X E
        return;
        //X E
    }
    //Start merge sort
    let mut fromStart:usize=0;
    let mut indices:Vec<usize> = vec![id,0,0,0];
    if (step[0]*2<shapeNumber) {
        indices[1]=(indices[0]-indices[0]%(step[0]*2));
    }
    let mut aux:Vec<usize> = vec![0,0,0,0];
    //Find both ends and starts and id from its half start.
    if (indices[1]+step[0]*2>shapeNumber) {
        if (step[0]==1) {
            //Copy this one.
            if (step[1]==0) {
                tempOrder[indices[0]]=drawOrder[indices[0]];
            } else {
                drawOrder[indices[0]]=tempOrder[indices[0]];
            }
            //X E
            return;
            //X E
        }
        //Figure this half
        aux[0]=indices[1];
        if (aux[0]+step[0]<shapeNumber) {
            aux[0]=aux[0]+step[0];
        } else if (aux[0]+step[0]/2<shapeNumber) {
            aux[0]+=step[0]/2;
        } else {
            //Copy this one.
            if (step[1]==0) {
                tempOrder[indices[0]]=drawOrder[indices[0]];
            } else {
                drawOrder[indices[0]]=tempOrder[indices[0]];
            }
            //X E
            return;
            //X E
        }
        //Assign based on which half.
        if (indices[0]>=aux[0]) {
            indices[2]=aux[0]-1;
            fromStart=indices[0]-aux[0];
            indices[3]=1;
        } else {
            fromStart=indices[0]-indices[1];
            indices[1]=aux[0];
            indices[2]=shapeNumber-1;
        }
    } else if (indices[0]>=indices[1]+step[0]) {
        indices[2]=indices[1]+step[0]-1;
        fromStart=indices[0]-(indices[2]+1);
        indices[3]=1;
    } else {
        fromStart=indices[0]-indices[1];
        indices[2]=indices[1]+step[0]*2-1;
        indices[1]+=step[0];
    }
    //Set initial sets.
    aux[2]=indices[1];
    aux[3]=indices[2];
    //Be efficient, only check step[1] once.
    if (step[1]==0) {
        //Loop and find where to input.
        while (indices[1]<indices[2]) {
            //Compare and eliminate all possibilities including current one. Round up.
            aux[1]=(indices[1]+indices[2]+1)/2;
            aux[0]=drawOrder[aux[1]];
            if (zDists[drawOrder[indices[0]]][0]>zDists[aux[0]][0]) {
                indices[2]=aux[1]-1;
            } else if (zDists[drawOrder[indices[0]]][0]<zDists[aux[0]][0]) {
                indices[1]=aux[1]+1;
            } else if (zDists[drawOrder[indices[0]]][1]>zDists[aux[0]][1]) {
                indices[2]=aux[1]-1;
            } else if (zDists[drawOrder[indices[0]]][1]<zDists[aux[0]][1]) {
                indices[1]=aux[1]+1;
            } else {
                //Equal numbers found, set before or after based on half.
                if (indices[3]==1) {
                    indices[1]=aux[1]+1;
                    aux[0]=1;
                    if (indices[1]+aux[0]<=aux[3]) {
                        while (zDists[drawOrder[indices[0]]][0]==zDists[drawOrder[indices[1]+aux[0]]][0]&&
                        zDists[drawOrder[indices[0]]][1]==zDists[drawOrder[indices[1]+aux[0]]][1]) {
                            if (indices[1]+aux[0]*2<=aux[3]) {
                                aux[0]*=2;
                            } else {
                                break;
                            }
                        }
                        while (aux[0] != 0) {
                            if (indices[1]+aux[0]<=aux[3]) {
                                if (zDists[drawOrder[indices[0]]][0]==zDists[drawOrder[indices[1]+aux[0]]][0]&&
                                zDists[drawOrder[indices[0]]][1]==zDists[drawOrder[indices[1]+aux[0]]][1]) {
                                    indices[1]+=aux[0];
                                }
                            }
                            aux[0]/=2;
                        }
                    }
                    if (indices[1]<=aux[3]) {
                        while (zDists[drawOrder[indices[0]]][0]==zDists[drawOrder[indices[1]]][0]&&
                            zDists[drawOrder[indices[0]]][1]==zDists[drawOrder[indices[1]]][1]) {
                            indices[1]+=1;
                            if (indices[1]>aux[3]) {
                                break;
                            }
                        }
                    }
                } else {
                    indices[1]=aux[1];
                    aux[0]=1;
                    if (indices[1] != 0) {
                        if (indices[1]-aux[0]>=aux[2]) {
                            while (zDists[drawOrder[indices[0]]][0]==zDists[drawOrder[indices[1]-aux[0]]][0]&&
                            zDists[drawOrder[indices[0]]][1]==zDists[drawOrder[indices[1]-aux[0]]][1]) {
                                if (indices[1]<aux[0]*2) {
                                    break;
                                } else if (indices[1]-aux[0]*2>=aux[2]) {
                                    aux[0]*=2;
                                } else {
                                    break;
                                }
                            }
                            while (aux[0] != 0) {
                                if (indices[1]>=aux[0]) {
                                    if (indices[1]-aux[0]>=aux[2]) {
                                        if (zDists[drawOrder[indices[0]]][0]==zDists[drawOrder[indices[1]-aux[0]]][0]&&
                                        zDists[drawOrder[indices[0]]][1]==zDists[drawOrder[indices[1]-aux[0]]][1]) {
                                           indices[1]-=aux[0];
                                        }
                                    }
                                }
                                aux[0]/=2;
                            }
                        }
                    }
                    while (indices[1]>aux[2]&&zDists[drawOrder[indices[0]]][0]==zDists[drawOrder[indices[1]]][0]&&
                        zDists[drawOrder[indices[0]]][1]==zDists[drawOrder[indices[1]]][1]) {
                        indices[1]-=1;
                    }
                    while (!(zDists[drawOrder[indices[0]]][0]==zDists[drawOrder[indices[1]]][0]&&
                        zDists[drawOrder[indices[0]]][1]==zDists[drawOrder[indices[1]]][1])||indices[1]<aux[2]) {
                        indices[1]+=1;
                    }
                }
                break;
            }
        }
        if (indices[1]==indices[2]) {
            //Compare and find proper place.
            aux[0]=drawOrder[indices[1]];
            if (zDists[drawOrder[indices[0]]][0]<zDists[aux[0]][0]||(zDists[drawOrder[indices[0]]][0]==zDists[aux[0]][0]&&zDists[drawOrder[indices[0]]][1]<zDists[aux[0]][1])) {
                indices[1]+=1;
            }
        }
    } else {
        //Loop and find where to input.
        while (indices[1]<indices[2]) {
            //Compare and eliminate all possibilities including current one. Round up.
            aux[1]=(indices[1]+indices[2]+1)/2;
            aux[0]=tempOrder[aux[1]];
            if (zDists[tempOrder[indices[0]]][0]>zDists[aux[0]][0]) {
                indices[2]=aux[1]-1;
            } else if (zDists[tempOrder[indices[0]]][0]<zDists[aux[0]][0]) {
                indices[1]=aux[1]+1;
            } else if (zDists[tempOrder[indices[0]]][1]>zDists[aux[0]][1]) {
                indices[2]=aux[1]-1;
            } else if (zDists[tempOrder[indices[0]]][1]<zDists[aux[0]][1]) {
                indices[1]=aux[1]+1;
            } else {
                //Equal numbers found, set before or after based on half.
                if (indices[3]==1) {
                    indices[1]=aux[1]+1;
                    aux[0]=1;
                    if (indices[1]+aux[0]<=aux[3]) {
                        while (zDists[tempOrder[indices[0]]][0]==zDists[tempOrder[indices[1]+aux[0]]][0]&&
                        zDists[tempOrder[indices[0]]][1]==zDists[tempOrder[indices[1]+aux[0]]][1]) {
                            if (indices[1]+aux[0]*2<=aux[3]) {
                                aux[0]*=2;
                            } else {
                                break;
                            }
                        }
                        while (aux[0] != 0) {
                            if (indices[1]+aux[0]<=aux[3]) {
                                if (zDists[tempOrder[indices[0]]][0]==zDists[tempOrder[indices[1]+aux[0]]][0]&&
                                zDists[tempOrder[indices[0]]][1]==zDists[tempOrder[indices[1]+aux[0]]][1]) {
                                    indices[1]+=aux[0];
                                }
                            }
                            aux[0]/=2;
                        }
                    }
                    if (indices[1]<=aux[3]) {
                        while (zDists[tempOrder[indices[0]]][0]==zDists[tempOrder[indices[1]]][0]&&
                            zDists[tempOrder[indices[0]]][1]==zDists[tempOrder[indices[1]]][1]) {
                            indices[1]+=1;
                            if (indices[1]>aux[3]) {
                                break;
                            }
                        }
                    }
                } else {
                    indices[1]=aux[1];
                    aux[0]=1;
                    if (indices[1] != 0) {
                        if (indices[1]-aux[0]>=aux[2]) {
                            while (zDists[tempOrder[indices[0]]][0]==zDists[tempOrder[indices[1]-aux[0]]][0]&&
                            zDists[tempOrder[indices[0]]][1]==zDists[tempOrder[indices[1]-aux[0]]][1]) {
                                if (indices[1]<aux[0]*2) {
                                    break;
                                } else if (indices[1]-aux[0]*2>=aux[2]) {
                                    aux[0]*=2;
                                } else {
                                    break;
                                }
                            }
                            while (aux[0] != 0) {
                                if (indices[1]>=aux[0]) {
                                    if (indices[1]-aux[0]>=aux[2]) {
                                        if (zDists[tempOrder[indices[0]]][0]==zDists[tempOrder[indices[1]-aux[0]]][0]&&
                                            zDists[tempOrder[indices[0]]][1]==zDists[tempOrder[indices[1]-aux[0]]][1]) {
                                            indices[1]-=aux[0];
                                        }
                                    }
                                }
                                aux[0]/=2;
                            }
                        }
                    }
                    while (indices[1]>aux[2]&&zDists[tempOrder[indices[0]]][0]==zDists[tempOrder[indices[1]]][0]&&
                        zDists[tempOrder[indices[0]]][1]==zDists[tempOrder[indices[1]]][1]) {
                        indices[1]-=1;
                    }
                    while (!(zDists[tempOrder[indices[0]]][0]==zDists[tempOrder[indices[1]]][0]&&
                        zDists[tempOrder[indices[0]]][1]==zDists[tempOrder[indices[1]]][1])||indices[1]<aux[2]) {
                        indices[1]+=1;
                    }
                }
                break;
            }
        }
        if (indices[1]==indices[2]) {
            //Compare and find proper place.
            aux[0]=tempOrder[indices[1]];
            if (zDists[tempOrder[indices[0]]][0]<zDists[aux[0]][0]||(zDists[tempOrder[indices[0]]][0]==zDists[aux[0]][0]&&zDists[tempOrder[indices[0]]][1]<zDists[aux[0]][1])) {
                indices[1]+=1;
            }
        }
    }
    //Place correctly.
    if (step[0]*2<shapeNumber) {
        aux[0]=indices[1]-aux[2]+fromStart+(indices[0]-indices[0]%(step[0]*2));
    } else {
        aux[0]=indices[1]-aux[2]+fromStart;
    }
    if (step[1]==0) {
        tempOrder[aux[0]]=drawOrder[indices[0]];
    } else {
        drawOrder[aux[0]]=tempOrder[indices[0]];
    }
    //X E
}
//X E
#[allow(warnings)]
fn main() {
    //Generate data.
    let size = random_range(2,10);
    println!("{}",size);
    let mut drawOrder=vec![0usize; size as usize];
    let mut tempOrder=vec![0usize; size as usize];
    let mut zDists=vec![[0.0f32,0.0f32]; size as usize];
    let mut index=size as usize;
    while index != 0 {
        index-=1;
        drawOrder[index]=index;
        zDists[index]=[random(),random()];
        while zDists[index][0] != zDists[index][0] || zDists[index][1] != zDists[index][1] {
            zDists[index]=[random(),random()];
        }
    }
    let mut step=vec![1usize,0usize];
    let mut num=0usize;
    while step[0]<size as usize {
        index=0;
        while index < (size as usize) {
            mergeSortMain(index,&step,size as usize,&mut zDists,&mut drawOrder,&mut tempOrder);
            index+=1;
        }
        if step[1]==0 {
            println!("{:?}",tempOrder);
        } else {
            println!("{:?}",drawOrder);
        }
        print!("[");
        num=step[0]*2;
        index=0;
        while index != size as usize {
            if (step[1]==1) {
                print!("({},{})",zDists[drawOrder[index]][0],zDists[drawOrder[index]][1]);
            } else {
                print!("({},{})",zDists[tempOrder[index]][0],zDists[tempOrder[index]][1]);
            }
            if index+1==size as usize {
                break;
            }
            if index==num-1 {
                print!("|");
                num+=step[0]*2;
            } else {
                print!(",");
            }
            index+=1;
        }
        print!("]");
        println!("");
        num=step[0]*2;
        index=0;
        while index != size as usize {
            if index != num-1&&index+1<size as usize {
                if (step[1]==1) {
                    if zDists[drawOrder[index]][0]<zDists[drawOrder[index+1]][0] {
                        println!("Error: {}",num);
                    } else if zDists[drawOrder[index]][0]==zDists[drawOrder[index+1]][0] {
                        if zDists[drawOrder[index]][1]<zDists[drawOrder[index+1]][1] {
                            println!("Error: {}",num);
                        }
                    }
                } else {
                    if zDists[tempOrder[index]][0]<zDists[tempOrder[index+1]][0] {
                        println!("Error: {}",num);
                    } else if zDists[tempOrder[index]][0]==zDists[tempOrder[index+1]][0] {
                        if zDists[tempOrder[index]][1]<zDists[tempOrder[index+1]][1] {
                            println!("Error: {}",num);
                        }
                    }
                }
            }
            if index==num-1 {
                num+=step[0]*2;
                if num>size as usize {
                    num=size as usize;
                }
            }
            index+=1;
        }
        step[0]*=2;
        if step[1]==0 {
            step[1]=1;
        } else {
            step[1]=0;
        }
    }
    index=0;
    while index<(size as usize) {
        if step[1]==1 {
            if !tempOrder.contains(&index) {
                println!("Error:{} missed",index);
            }
        } else {
            if !drawOrder.contains(&index) {
                println!("Error:{} missed",index);
            }
        }
        index+=1;
    }
    println!("X E.");
    //X E
}
//X E

main() is a test function. All problems are in that mergeSortMain. I had a working version that worked differently if you want that. X E.

parasyte · August 20, 2025, 8:59pm

I will be honest, I cheated and copied your post and code to ChatGPT and it found and corrected the bug (as far as I can tell... The main test function no longer prints errors.)

Because the use of AI tools is controversial, I'll ask your permission to reply with the results discovered by the LLM.

On the other hand, I don't have a whole lot of time to review this code myself. So, I'll leave it at that until I can approach this more closely, later.

maybeJosiah · August 20, 2025, 9:57pm

Feel free to use AI, as long as it works, my email is maybejosiah@aol.com or you can simply post it here. I would like to acknowledge your help and the AI's though. I know ChatGPT's terms and they allow everything I need. That if this works but I may have to test first and also be sure it is as fast and efficient as it should be. If you can believe it I tried to make a whole Radix sort with Grok AI on X. It is not good at sorting. TL;DR: Thanks, let's share. X E.

maybeJosiah · August 20, 2025, 11:11pm

What I have tried now: simple increment/decrement until at an end with equals, switching indices[3]=1 on which, Grok 4, ChatGPT, it is so obviously wrong only in the equals section but I do not know how to fix it. I doubt yours would be correct. Go for it but I doubt it. It is 100% accurate when things are unique, I tested. It seems I don't know how to do this. Now I tried GitHub Copilot. X E.

maybeJosiah · August 20, 2025, 11:27pm

//Equal numbers found, set before or after based on half.

Only stuff in {} brackets with that is faulty. There are two. In fact, that is the bulk of the code, feel free to start from scratch only in that. X E.

parasyte · August 20, 2025, 11:43pm

Sure, here's the code that ChatGPT output. Disclaimer: I have not proofread the code or analysis.

You were right: the equal-elements path was the culprit. Your original mergeSortMain tries to “scan past equals” with a bunch of bound tweaks; that can skip slots and cause collisions/missed indices.

I replaced that whole branchy block with a stable rank-based placement that works per element:

Treat each block [start, end) with midpoint mid (run length = step[0]).

For a left-half element x, its final position is:
start + (index_in_left) + (# of right elements strictly greater than x).
(Left comes before equal right elements for stability.)

For a right-half element x, its final position is:
start + (index_in_right) + (# of left elements greater-or-equal to x).

Because each half is already sorted (descending by z[0], then z[1]), we can get those counts with two tiny binary searches—no linear scans, no off-by-one landmines. Trailing partial runs just copy through.

I kept your double-buffer contract (step[1] switches read/write) and your descending lex order (z[0], z[1]).

The updated code is in the canvas. Try it in the Rust playground with your existing main(); it should preserve all indices and handle ties correctly. If you want, I can also show a branchless comparator version or convert this into a safe, parallel chunk using rayon without touching your external interface.

maybeJosiah · August 20, 2025, 11:53pm

Sorry to say this but it works but is less efficient than I want, it should eliminate half+1 every time. Maybe I can model by this though because it works. Thank you. X E.

maybeJosiah · August 21, 2025, 12:07am

I made Grok on X adjust it for me and I now have a working merge sort for this with hi=m-1 or for bounding, hi=m. Thank you again, how should I acknowledge you? Feel free to email me if you want to privately do stuff. Permission to open source this? X E.

parasyte · August 21, 2025, 12:32am

This is a tough question. I didn't do anything worth acknowledging. If you wish, you can use @parasyte here or on GitHub, with a disclosure that I used ChatGPT 5. But I am happy to release you of any obligation.

danjl1100 · August 21, 2025, 3:23pm

Just wanted to throw in, as far as permission to use code posted here / license questions, section 3 in the terms of service of this forum clarify:

User contributions made on or after 2020-07-17 are dual-licensed under the MIT and Apache 2.0 licenses unless otherwise stated. The licenses were explicitly chosen to ensure that text from comments on this forum may be included in RFCs, which are also licensed in the same fashion, per RFC 2044. This license also implies that content from the comments on this forum (including code snippets) can be incorporated into the rust-lang/rust repository (or other repositories using a similar license).

jdahlstrom · August 21, 2025, 4:54pm

However, technically the user of an LLM does not hold copyright to the content generated by an LLM, and thus cannot give consent to the licensing. And the LLM is not a legal entity so cannot hold copyright (or consent to licensing) either. It's currently a legal black hole, but as far as I can see, LLM-generated content does not constutitute original work and thus is not copyrighted or copyrightable at all. Which means any license conditions do not apply to those parts.

ZiCog · August 21, 2025, 5:19pm

Intersting.

For many decades now traditional software companies do the following:

Craft a program in some source language, like C or C++.
Feed that source into a compiler that transforms that source into some binary executable.
Sell copies of that binary, while using copyright protection to prevent people from just copying it for free.

Notably, the originally crafted source is never shown to anyone.

Hypothetically then there is me:

Crafts prompts in English or whatever for some program I have in mind.
Feed those prompts into an LLM that transforms those prompts into some source code in some programming language. Feed that source into a compiler that transforms that source into some binary executable.
Sell copies of that binary, while using copyright protection to prevent people from just copying it for free.

Notably, the originally crafted prompts and programming language source is never shown to anyone.

I conclude then that I have the copyright over those binaries I ship as much as the likes of MS have copyright over the software they ship.

Basically what I'm saying is that introducing AI is just another step in the line from my source (which is now prompts) to the end binary product. A step like any other, the IR or ASM the compiler generates for example.

In fact, if the AI were up to it I would not need the intermediate programming language source in C++ or Rust or whatever any more than I need a compilers IR or ASM intermediate stages. The AI could go directly from my prompts to executable binary.

Why does this argument not fly?

parasyte · August 21, 2025, 8:11pm

It's a huge mess.

My reading of the argument against that boils down to "LLM output is copyright infringement" and therefore implies that using the output voids any copyright you claim over any further artifacts in the chain.

But we can scrutinize this line of reasoning with the same logic. An unmeasurable but nontrivial amount of existing code deployed in the wild ^[1] violates the licensing terms of stackoverflow, which says that all user contributions are licensed under one of the CC BY-SA licenses. I.e., it is a license violation to not attribute and copyleft the product that any stackoverflow code appears in. (Just my person understanding, though I am not a lawyer.)

Who knows.

Without regard to LLM involvement. Stackoverflow predates them by around a decade. ↩︎

ZiCog · August 21, 2025, 8:38pm

I guess a counter argument would be that the AI we have relies on hoovering up everything, with total disregard to its copyright status and then regurgitating derived work from it as answers to our prompts.

In the extreme I could ask an AI to "Write me a huge book about war and peace" and the AI would give me the text of the famous book "War and Peace".

maybeJosiah · August 22, 2025, 6:27pm

Whatever terms AIs have, it works now and for that I am grateful, I kind of modified it beyond recognition now anyway, it was for RinomXE Slang shaders 2 version soon to be on GitHub and now works nearly as my original one did so practically who cares about AI licensing?

system · November 20, 2025, 6:27pm

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.

Topic		Replies	Views
Missing life time specifiers: borrowing from return	7	794	August 8, 2023
Create merge sort in rust	16	4771	November 21, 2021
Borrowing problem from porting some C++ code help	20	1510	January 12, 2023
Mergesort not working help	2	900	March 28, 2020
Unexpected parallel sort performance help	3	160	October 8, 2025

Why is this merge sort not sorting equals correctly?

Related topics