DEV Community

Cover image for Making Sense of Merge Sort [Part 1]

Making Sense of Merge Sort [Part 1]

Vaidehi Joshi on June 05, 2017

If you’ve been reading this series sequentially, then there’s a good chance that over the course of the past few weeks, you’ve thought more about s...
Read full post
Collapse
 
sarwarbhuiyan profile image
Sarwar Bhuiyan •

Hi there, I think the merge function you implemented is wrong. When you started to merge the individual items of each partition you still have to compare the items of each partition before putting into the merged partiton. In your code you simply shifted each partition individually into the merged partiton. Should be something like this (from Wikipedia)

TopDownMerge(A[], iBegin, iMiddle, iEnd, B[])
{
i = iBegin, j = iMiddle;

// While there are elements in the left or right runs...
for (k = iBegin; k < iEnd; k++) {
    // If left run head exists and is <= existing right run head.
    if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) {
        B[k] = A[i];
        i = i + 1;
    } else {
        B[k] = A[j];
        j = j + 1;    
    }
}
Enter fullscreen mode Exit fullscreen mode

}

Collapse
 
vaidehijoshi profile image
Vaidehi Joshi •

I think you might have misread a section of the function -

if (rightArray[0] < leftArray[0]) {
   array[index++] = rightArray.shift();
} else {
   array[index++] = leftArray.shift(); 
}
Enter fullscreen mode Exit fullscreen mode

Here, I'm both comparing the elements of each partition and also merging it in. This is still a merge sort function, it has just been rewritten into simplified bits of code, rather than implemented in one single while loop.

Collapse
 
sarwarbhuiyan profile image
Sarwar Bhuiyan •

Thanks. Missed the shift() function definition which is effectively using it like a stack so it means you're cutting it down instead of traversing the array.

Thread Thread
 
jgaskins profile image
Jamie Gaskins • • Edited

No, not like a stack. A stack gets pushed and popped from the end. She's pulling from the front, but not even in the sense of a queue. It's just an array that happens to get consumed based on which one has the lowest first value.

She treats merge as a private API for this algorithm, giving it knowledge that leftArray and rightArray belong to the mergeSort algorithm so it can do whatever it needs to with them. If I had to guess, I'd say it looks like a refactoring, pulled out into its own function after having to do the same operation with both segments of the original array.

The most important thing to keep in mind is that she's not optimizing the code for execution time, space, or anything involving a computer. Instead, she's optimizing for readability for the audience she's targeting with this blog series — that is, developers who don't have a background in CS. The example you pasted above, while apparently correct and probably efficient, is a poor teaching tool for that audience. A single iterator for the main array and only working with the front of the two other arrays is less cognitive load than having three iterators moving through three arrays at three different paces.

Collapse
 
4nduril profile image
Tobias Barth • • Edited

Thank you so much for this series!

I also was tempted by this article to implement a mergesort myself (while heavily relying on yours of course). I think it's a bit shorter than yours but also, for me more importantly, it is not mutating the array(s) that are fed in which I didn't like. OTOH it maybe uses more space. So here it is:

function mergesort (array = []) {
    if (array.length < 2) return array;

    const mid = Math.floor(array.length / 2);
    const left = mergesort(array.slice(0, mid));
    const right = mergesort(array.slice(mid));

    const merged = [];

    while (left.length && right.length) {
        merged.push(left[0] < right[0] ? left.shift() : right.shift());
    }

    while (left.length) {
        merged.push(left.shift());
    }

    while (right.length) {
        merged.push(right.shift());
    }

    return merged;
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
theprash profile image
Prash •

As a developer with no CS background, I'm really enjoying these articles. Now I actually want to try implementing a merge sort myself. Thanks!

Collapse
 
ben profile image
Ben Halpern •

Heck yes!

Collapse
 
vaidehijoshi profile image
Vaidehi Joshi •

Yes! I totally support this decision, Prash. And would love to see your implementation when you're done :)

Thread Thread
 
theprash profile image
Prash •

OK, I finally got round to it. This is an implementation in my language of choice, F#. Note that I didn't read the JS implementation. This is purely based on your description of recursive splitting and merging, and so there is no mutation here. Just a lot of building up of arrays and lists, so it's probably not very efficient. It was fun to write, though!

let split xs =
    let mid = Array.length xs / 2
    (xs.[0 .. mid - 1], xs.[mid .. xs.Length - 1])

let rec merge xs ys acc =
    match xs, ys with
    | []      , []       -> List.rev acc
    | x :: xs', []
    | []      , x :: xs' -> merge xs' [] (x :: acc)
    | x :: xs', y :: ys' ->
        if x < y then merge xs' ys  (x :: acc)
        else          merge xs  ys' (y :: acc)

let rec mergeSort xs =
    match split xs with
    | [| |], [| |] -> [ ]
    | [| |], [|x|]
    | [|x|], [| |] -> [x]
    | [|x|], [|y|] -> merge [x] [y] []
    | xs   , ys    -> merge (mergeSort xs) (mergeSort ys) []
Enter fullscreen mode Exit fullscreen mode
Collapse
 
rafaelcg profile image
Rafael Corrêa Gomes •

Thanks for sharing Vaidehi, I'm anxious to the part 2!

Collapse
 
Sloan, the sloth mascot
Comment deleted