fluxsort Incorrect constraint in comment

I'm assuming the comment is just wrong cause everything seems to sort fine, but https://github.com/scandum/fluxsort/blob/000dd5ac1ed8af60be82a2e43230bd74cb8adc56/src/quadsort.c#L143 is not accurate.

Was fuzzing my implementation with an assert that matched that comment. With this Input:

Input

```c [58506920276529, 8743316464009216, -17591310022656, 4294971590967295, 4410770279176929279, -2459565879408445385, -2459565876494606870, -2459565876494606883, 4071312570059882495, 3689047535620468784, 18911841442149940, 3978145443681927168, -2199023321087, 3472328296227672063, 3978164135374500144, 223338574136, 2676604961529266176, 3761403986182481189, 3905803080472999222, -2459566622437263555, -2459565876494603555, -2459565876494606883, -9208394266114523171, 3612221359652876344, 4841431409190375987, 3834309528548016128, -562949970198217, 3472328296225570815, 3839094601846698032, 57174674978871, 2681339424238731264, 3761403989854224421, 3472556787670988086, 3472328296241299455, 2676619427804360752, 2676586510972953893, -61602178969575168, 3472328296227733503, 2676586524043194416, 10455416058488101, 3685392711537729761, 3530822105714472500, 2089669678236841011, 9223328985190553648, 3519801534652668120, -2821266740685036240, -2821446617553436456, -2821464277639440168, 3689348694493681880, -281474117717224, 5931893837159150387, 3834342646677131858, 2320253419869190199, 2320253415708898614, -418780682174122686, 3472328296227745840, 3472328296227680304, 9629747033289008, 290482175965396992, 5938649572163342930, 3544385924743116370, 3474587814197211954, 15823300577997618, 7740398493683560452, 7740398493674204011, 7740398493623872363, 3489000445436455787, 3472328296227680560, 3472328296227680304, 3689064934532984854, 3487284, 1099511852037570560, 3905802973011246848, -2459566622437263555, -2459579070634136867, -2459565876494606883, 14977770740252637, 0, 0, 0, 0, 7638104968037072896, 3472328331926437888, -1099511615440, 14697206288228111, 4683743612465315824, 3682872471335210818, -2508451974442305996, -2459565876276503075, -2459565876494606883, 3905747326590639581, 3472328296228225077, 4050764896192901665, 3761490851272868656, -1099491232458, 3472328157980262397, 3761405300627746864, 3746999499415303495, 576460752303423488, -61602178432424650, 3834313933946368816, 3905803062383476608, -58492919086088139, 3472328296227733503, 2676586524043194416, 10455416058488101, -240633511599903, 3472328296227680511, 2676586395512877360, -2233744573706787547, 3761390955251696928, 3688729569784771894, 3466927286001153588, -2846275132668716840, 3472513738565277912, -2821266740684990427, -2821267443329007616, -2821267512313718568, 1743793775248136408, 3746993790463980339, 5931894171412607795, 3978145573049619026, 3900173567969472568, 4764864696408356661, 3529186245818726197, 3472328296227680560, 3472328296227680304, 37616199348785, 5909857407109955584, 5931920561001353810, 3616724959414924598, 3616452310545604659, 288292185919594547, 7740398493674240560, 7740398493674204011, 7740398493674007403, 3472393421810527083, 3472328296227680305, 1598830851241553968, 3761405299872772144, 13622, 4294968172021760, 4410770279176929279, -2459565879408445385, -2459565928034214422, -2459565876494606883, 58506916954111, 0, 0, 0, 0, 29836347531394816, 3472328296367128576, 8753086948596392240, 8753160913407277433, 8753160913407277433, 8753160990717181817, 8753160913407277433, 8753160913407277433, 2038004089, 2700323012317544448, 3906931183664181503, 3761403989854224437, 3472556787670988086, 3472328296241299455, 2676598537083433008, 2676586510972953893, 2676586394485645568, -548863069133, -140508945698000, -2821267393520062436, -2821266740684990248, -2821266740684990248, 3978324270223775960, 429496730408464440, 3689318028416332595, -72036483414681549, 5931808268559266815, 3914281642739520082, 3761122721844967221, -2459756837814715082, -2459565876493754915, -2459565876494606883, 3834309309504675293, 2391464385658763392, 8753160912278663986, 8753160913407277433, 8753160913407277433, 8755131238244252025, 8753160913407277433, 8753160913407277433, 8753160913407277433, 3530581836541032825, -9208394248050297805, 3834309527222616063, -228487965237376, 3472328296227680511, 2676586395194110256, 3905803067236295973, 8753160913407277433, 8753160913407277433, 8758227495300987257, 8753160913407277433, 8753160913407277433, 133562636007801, 8753036146864291840, 3834309527222560121, 3530822105714472504, -548863069133, 3472329188772360240, 3472329395739308080, 2684186219380024613, 2676552107141637413, -35970290098690779, -9208394265264062465, -2864050939975892993, -2821266740684990248, -2821266740684990248, -2821364425421170472, -2233732431650212043, 1671736181679916533, 1383505805075231539, 302078945019297536, 5938649572163342930, 3544385924743116370, 3472337122603971634, -2459565820660032035, -2459565876494606883, 3747135626887945693, 3472328296367142198, 8753086948596392240, 8753160913407277433, 8753160913407277433, 8753160913407277433, 8753160913407277440, 8753160913407277433, 8753160913407277433, 2700323014221330809, 3906931183664181503, 3761403989854224437, 3472556783912891702, 3472328296241299455, 2676598537083433008, 2676586510972953893, 2676586394485645568, -548863069133, -140508945698000, -2821264094985179108, -2821266740684990261, -2821266740684990248, 5909902708277565531, 5931920561001353810, 3616724959414924598, 3616452310545604659, 3544394716508463155] ```

The final parity merge has a left of size 128 and a right of size 127. So in this case, left is one larger than right.

Note: that input was fed directly into quadsort_prim

Jul 26 '24 23:07 bhansconnect

Thanks, that's a nice catch. It should sort fine, but I went ahead and fixed it as I'm not comfortable with it.

Jul 27 '24 13:07 scandum

Just for reference, I changed my assert to check that the values are within 1 of each other and ran a lot more fuzzing. No failures found in 200+ million fuzz attempts. So I think the sort is correct even with left being 1 larger than right for parity merge.

Jul 27 '24 17:07 bhansconnect

Yeah, looking at the code a bit more, if left is 1 greater than right, the final tail tail_branchless_merge is unnecessary. That said, running it an extra time doesn't break anything, it just copies data redundantly.

So the most correct version of the function would add a guard around the last tail_branchless_merge of if(left >= right).

Technically speaking, at the cost of a redundant copy, this function could always go to the max of the length of right or left.

Jul 27 '24 18:07 bhansconnect