First question here, and yes this is a homework question. We are tasked with performing merge sort on an array (which I am familiar with), but in a way I am unsure of how to do. Usually I would have a separate merge and merge sort function, and use the two. However, it sounds like he wants everything in one method? I was just hoping maybe someone could help clear things up for me, or put them into terms I can better understand.
From the assignment:
you will need to implement a non-recursive version of merge-sort algorithm. Arrange two nested loops to accomplish this task. The outer loop should provide the size of segments for merging. The inner loop should take care of selecting positions of segments. The inner loop should start at the left edge and move your segments to the right. Arrange appropriate values of variables left, middle, right, so that sorting is accomplished just by iterating the call merge(a,left,middle,right).
I hate to be so vague, but I really don't understand any of what he's saying. First, what is meant by "outer loop should provide the size of segments"? How does a loop provide anything? What about the next sentence - what does he mean by segments? The data?
I'm not asking for code, but any psuedocode would be really helpful.
If anyone could try and decipher what he means, I'd appreciate it. I've already emailed him about it, but it's been a few hours and I've yet to hear back.
Thank you!