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)
// 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;
}
}
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.
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.
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.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
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;
}
I think you might have misread a section of the function -
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
whileloop.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.
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
mergeas a private API for this algorithm, giving it knowledge thatleftArrayandrightArraybelong to themergeSortalgorithm 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.