StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POMergesort that saves memory
text
Body
copied!<p>I'm taking an Algorithms class and the latest homework is really stumping me. Essentially, the assignment is to implement a version of merge sort that doesn't allocate as much temporary memory as the implementation in CLRS. I'm supposed to do this by creating only 1 temp array at the beginning, and put all the temp stuff in it while splitting and merging.</p> <p>I should also note that the language of the class is Lua, which is important because the only available data structures are tables. They're like Java maps in that they come in key-value pairs, but they're like arrays in that you don't have to insert things in pairs - if you insert only one thing it's treated as a value, and its key will be what its index would be in a language with real arrays. At least that's how I understand it, since I'm new to Lua as well. Also, anything at all, primitives, strings, objects, etc can be a key - even different types in the same table.</p> <p>Anyway, 2 things that are confusing me:</p> <p>First, well, how is it done? Do you just keep overwriting the temp array with each recursion of splitting and merging?</p> <p>Second, I'm really confused about the homework instructions (I'm auditing the class for free so I can't ask any of the staff). Here are the instructions:</p> <ol> <li><p>Write a top level procedure merge_sort that takes as its argument the ar- ray to sort. 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 tem- porary space, and the start and finish indexes within which this call to merge_sort_1 should work.</p></li> <li><p>Now write merge_sort_1, which computes the midpoint of the start–finish interval, and makes a recursive call to itself for each half. After that it calls merge to merge the two halves. The merge procedure you write now will be a function of the permanent array and the temporary array, the start, the midpoint, and the finish. It maintains an index into the temporary array and indices i, j into each (sorted) half of the permanent array. It needs to walk through the temporary array from start to finish, copying a value either from the lower half of the permanent array or from the upper half of the permanent array. It chooses the value at i in the lower half if that is less than or equal to the value at j in the upper half, and advances i. It chooses the value at j in the upper half if that is less than the value at i in the lower half, and advances j. After one part of the permanent array is used up, be sure to copy the rest of the other part. The textbook uses a trick with an infinite value ∞ to avoid checking whether either part is used up. However, that trick is hard to apply here, since where would you put it? Finally, copy all the values from start to finish in the temporary array back to the permanent array.</p></li> </ol> <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. 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> <p>I hope I've made some sense. Thanks everyone!</p>

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