1

I've been trying to understand the non-recursive MergeSort algorithm after recently coding the recursive version. My AP book doesn't provide too much info or examples on this topic so I was hoping someone could help me clear things up a bit.

What does my book mean by the following: "In a non-recursive mergeSort method. We divide the list into two equal-sized parts and sort each with the selection sort, then merge the two using an algorithm to be discussed in part B."

Does one always divide an array into two pieces in a non-recursive mergeSort method (and then sort them accordingly), or are there cases like the recursive version where you keep dividing until you get to array.length of 2 or 1?

Book code: 

void mergeSort (ArrayList <Integer> A, int first, int last){
   int mid;

   mid = (first + last) / 2;
   selectionSort (A, first, mid);
   selectionSort (A, mid+1, last);
   merge (A, first, mid, last);
 }

If you always divide the array into 2 and then sort how is this efficient? What happens if your array contains thousands of values . . . wouldn't recursive be better off as it sorts the values in smaller pieces?

Book demonstration:

enter image description here

Cristian Gutu
  • 1,221
  • 1
  • 11
  • 24

2 Answers2

1

From my understanding what the book means is that you can divide the array in half, sort each array using selection sort, and then merge these two halves using the merge algorithm (which would be the same as for recursive mergesort). It may only want to show how the merging works.

However this implementation is NOT a mergesort. It's asymptotic efficiency is going to be far worse than mergesort's O(n log(n)) as selection sort is O(n^2).

But it is possible to do a mergesort without the use of recursion - you could use iterations. See the implementation here.

Kuba Spatny
  • 26,618
  • 9
  • 40
  • 63
0

I think this example is being used purely to demonstrate a single step of mergesort. With the two halves being sorted with selection sort, this implementation has very little of the "flavor" of mergesort, and certainly won't have mergesort's asymptotic complexity guarantees.

If you've already coded up a recursive mergesort, I don't think this example has much relevance to you. Actual non-recursive mergesort looks very different from this.

Sneftel
  • 40,271
  • 12
  • 71
  • 104