StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<blockquote> <p>First, well, how is it done? Do you just keep overwriting the temp array with each recursion of splitting and merging?</p> </blockquote> <p>Yes, the temp array keeps getting overwritten. The temp array is used during the merge phase to hold the merge results that are then copied back into the permanent array at the end of the merge.</p> <blockquote> <p>Number 2 is confusing because I have no idea what merge_sort_1 is supposed to do, and why it has to be a different method from merge_sort.</p> </blockquote> <p><code>merge_sort_1</code> is the recursive center of the recursive merge sort. <code>merge_sort</code> will only be a convenience function, creating the temp array and populating the initial start and finish positions.</p> <blockquote> <p>I also don't know why it needs to be passed starting and ending indexes. In fact, maybe I misread something, but the instructions sound like merge_sort_1 doesn't do any real work.</p> <p>Also, the whole assignment is confusing because I don't see from the instructions where the splitting is done to make 2 halves of the original array. Or am I misunderstanding mergesort?</p> </blockquote> <p>The recursive function <code>merge_sort_1</code> will only work on a portion of the passed in array. The portion it works on is defined by the start and ending indexes. The mid-point between the start and end is how the array is split and then split again on recursive calls. After the recursive calls for the upper and lower half are complete the two halves are merged into the temp array and then copied back to the permanent array.</p> <p>I was able to write the merge sort in Lua as described and can comment on my implementation. It does seem as through the instructions were written as if they were comments in or about the teacher's implementation.</p> <p>Here is the <code>merge_sort</code> function. As I said, it is only a convenience function and I feel is not the meat of the problem.</p> <pre><code>-- Write a top level procedure merge_sort that takes as its argument -- the array to sort. function merge_sort(a) -- It should declare a temporary array and then call merge_sort_1, -- a procedure of four arguments: The array to sort, the one to use -- as temporary space, and the start and finish indexes within which -- this call to merge_sort_1 should work. merge_sort_1(a,{},1,#a) end </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload