0

I've searched a lot for this but I have found nothing so far. I had to ask my question here.

In my current code I get the result by dividing by 2.

Sample data : $example = [50,20,87]

Expected result : 20,50,87

What I expect is how to do this by dividing by 3 instead of 2

Here is the code :

function merge_sort(&$arrayToSort)
{
    if (sizeof($arrayToSort) <= 1)
        return $arrayToSort;

    // split our input array into two halves
    // left...
    $leftFrag = array_slice($arrayToSort, 0, (int)(count($arrayToSort)/2));
    // right...
    $rightFrag = array_slice($arrayToSort, (int)(count($arrayToSort)/2));

    // RECURSION
    // split the two halves into their respective halves...
    $leftFrag = merge_sort($leftFrag);
    $rightFrag = merge_sort($rightFrag);

    $returnArray = merge($leftFrag, $rightFrag);

    return $returnArray;
}


function merge(&$lF, &$rF)
{
    $result = array();

    // while both arrays have something in them
    while (count($lF)>0 && count($rF)>0) {
        if ($lF[0] <= $rF[0]) {
            array_push($result, array_shift($lF));
        }
        else {
            array_push($result, array_shift($rF));
        }
    }

    // did not see this in the pseudo code,
    // but it became necessary as one of the arrays
    // can become empty before the other
    array_splice($result, count($result), 0, $lF);
    array_splice($result, count($result), 0, $rF);

    return $result;
}
Markus AO
  • 4,771
  • 2
  • 18
  • 29
Jack Forest
  • 41
  • 7
  • 1
    Please add some proper examples of what data you want to merge/sort and the expected result from that data. You should also include any attempt you've made (since this isn't a free coding service where we just hand you code, but rather where we help you fix specific issues you run into with your existing implementation attempt). – M. Eriksson Dec 25 '21 at 11:47
  • No this does not answer my question – Jack Forest Dec 25 '21 at 11:48
  • included, M. Eriksson – Jack Forest Dec 25 '21 at 11:54
  • Sample data and expected results, please. – Markus AO Dec 25 '21 at 12:06
  • Sample is added. I'm surprised no one knows about merge sort ! It is an important lesson in computer science and is taught by many professors in university ! – Jack Forest Dec 25 '21 at 12:11
  • The fact that you aren’t finding many examples would lead me to believe that although this might be important academically, it isn’t as important in the business-world. Although not rare, it is uncommon to have data of significant size without a _system_ that is capable of sorting it, and in fact, more efficient, especially once transport is taken into account. There are times when specialized sorting is needed, but those too, are either one-timers, or where we’re still talking about fractions of seconds difference. – Chris Haas Dec 25 '21 at 14:52
  • My previous comments which I deleted were focused more on JS which you had originally tagged this on. But I did find several [examples](https://www.geeksforgeeks.org/3-way-merge-sort/) online that seem like they should pretty easily port over to PHP, if someone was so inclined. – Chris Haas Dec 25 '21 at 14:54
  • For those that voted to close, this is not a three-way merge, like how a diff is done, this is a sorting algorithm that sorts subsets and merges them together. To the OP, I think you might be able to replace your two slice calls with an `array_chunk` to get three arrays. Not sure on the splice part, however. – Chris Haas Dec 25 '21 at 17:21
  • Thank you Chris Haas. I think only you could understand this. – Jack Forest Dec 25 '21 at 18:51
  • 1
    @ChrisHaas yet to come across a use case that calls for implementing merge sort. To "get the job done" with the example here, `sort($example`);` and done. Function calls are expensive, and an in-PHP sort function with multiple core and user function calls would make the sort an order of magnitude slower; and would only make sense _if desired results can't be attained by available built-in sort algorithms_ (or as an exercise). Reading up though, being curious, here's a SO thread the OP may find useful: https://stackoverflow.com/questions/9401019/writing-merge-sort-in-php – Markus AO Dec 25 '21 at 19:18
  • 1
    @MarkusAO, I 100% agree, I have zero use for this either. Like I said in my other comments, if I’m sorting data of any significant size, I’ll almost always be seeding from a database. The OP appears to be coming from a pure academic/theoretical space, and although the sample data isn’t ideal, for that space it is the smallest set that shows a 3-way. We tend to lean more towards practical applications on this site, so I’m fine closing this, I just wanted to make sure people were aware of what they were asking vs the reasons they were closing. – Chris Haas Dec 26 '21 at 13:59

0 Answers0