Non-recursive merge sort with two nested loops - how?

Question

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!

Answer 1

It's not so difficult. Consider the recursive merge:

       +-+-+-+-+-+-+-+-+
       | | | | | | | | |
       +-+-+-+-+-+-+-+-+
            /     \               split
    +-+-+-+-+     +-+-+-+-+
    | | | | |     | | | | |
    +-+-+-+-+     +-+-+-+-+
      /   \         /  \          split
  +-+-+  +-+-+  +-+-+  +-+-+
  | | |  | | |  | | |  | | |
  +-+-+  +-+-+  +-+-+  +-+-+
  / \     / \     / \     / \     split
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
| | | | | | | | | | | | | | | |
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
  \ /     \ /     \ /     \ /     merge
  +-+-+  +-+-+  +-+-+  +-+-+
  | | |  | | |  | | |  | | |
  +-+-+  +-+-+  +-+-+  +-+-+
      \   /         \  /          merge
    +-+-+-+-+     +-+-+-+-+
    | | | | |     | | | | |
    +-+-+-+-+     +-+-+-+-+
            \     /               merge
       +-+-+-+-+-+-+-+-+
       | | | | | | | | |
       +-+-+-+-+-+-+-+-+

If you notice, when you split, you don't really do anything. You just tell the recursive function to partially sort the array. Sorting the array consists of first sorting both halves and then merging it. So basically, what you have is this:

+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
| | | | | | | | | | | | | | | |
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
  \ /     \ /     \ /     \ /     merge
  +-+-+  +-+-+  +-+-+  +-+-+
  | | |  | | |  | | |  | | |
  +-+-+  +-+-+  +-+-+  +-+-+
      \   /         \  /          merge
    +-+-+-+-+     +-+-+-+-+
    | | | | |     | | | | |
    +-+-+-+-+     +-+-+-+-+
            \     /               merge
       +-+-+-+-+-+-+-+-+
       | | | | | | | | |
       +-+-+-+-+-+-+-+-+

Now from here it should be obvious. You first merge elements of the array 2 by 2, then 4 by 4, then 8 by 8 etc. That is the outer for gives you 2, 4, 8, 16, 32, ... (which is what it calls size of the segment because the i of the loop contains that number) and the inner for (say with iterator j) goes over the array, i by i merging array[j...j+i/2-1] with array[j+i/2..j+i-1].

I wouldn't write the code since this is homework.

Edit: a picture of how the inner for works

Imagine if i is 4, so you are at this stage:

  +-+-+  +-+-+  +-+-+  +-+-+
  | | |  | | |  | | |  | | |
  +-+-+  +-+-+  +-+-+  +-+-+
      \   /         \  /          merge
    +-+-+-+-+     +-+-+-+-+
    | | | | |     | | | | |
    +-+-+-+-+     +-+-+-+-+

you will have a for that once gives you 0(which is 0*i) as j and then 4 (which is 1*i) as j. (if i was 2, you would have j going like 0, 2, 4, 6)

Now, once you need to merge array[0..1] with array[2..3] (which is formulated by array[j..j+i/2-1] and array[j+i/2..j+i-1] with j = 0) and then array[4..5] with array[6..7] (which is formulated by the same formulas array[j...j+i/2-1] and array[j+i/2..j+i-1] because now j = 4) That is:

i = 4:
       +-+-+-+-+-+-+-+-+
       | | | | | | | | |
       +-+-+-+-+-+-+-+-+
        ^ ^ ^ ^ ^ ^ ^ ^
        | | | | | | | |
       / / / /   \ \ \ \
     (j  =  0)   (j  =  4)
      | | | |     | | | |
      j | | |     j | | |
      | | | j+i-1 | | | j+i-1
      | | j+i/2   | | j+i/2
      | j+i/2-1   | j+i/2-1
      | | | |     | | | |
      | | | |     | | | |
      \ / \ /     \ / \ /
       v   v       v   v
       merge       merge

Hope this is clear at least a little.

---

Side help: Just a hint if you don't really know how for works:

for (statement1; condition; statement2)
{
    // processing
}

is like writing

statement1;
while (condition)
{
    // processing
    statement2;
}

So, if you always wrote

for (int i = 0; i < 10; ++i)

it meant starting from 0, while i is smaller than 10, do something with i and then increment it. Now if you want i to change differently, you just change statement2 such as:

for (int i = 1; i < 1024; i *= 2)

(Try to understand how that final for works based on its equivalent while that I wrote you)

Answer 2

Here's my lazy, iterative/bottom-up merge-sort implementation that uses std::merge:

template<class InIt, class OutIt>
OutIt mergesort(InIt begin, InIt const end, OutIt o /* auxiliary buffer */)
{
    ptrdiff_t j;
    for (j = 0; begin != end; ++begin, ++j)
    {
        for (ptrdiff_t n = 1; n <= j && j % (n * 2) == 0; n *= 2)
        {
            o = std::merge(o - n * 2, o - n, o - n, o, begin - n * 2);
            o = std::swap_ranges(begin - n * 2, begin, o - n * 2);
        }
        *o = *begin;
        ++o;
    }
    --j;
    for (ptrdiff_t m = 1, n = 1; n <= j; n *= 2)
    {
        if (j & n)
        {
            o = std::merge(o - (m + n), o - m, o - m, o, o - (m + n));
            o = std::swap_ranges(begin - (m + n), begin, o - (m + n));
            m += n;
        }
    }
    return o;
}

Here's an in-place version that uses std::inplace_merge:

template<class InIt>
InIt inplace_mergesort(InIt begin, InIt const end)
{
    ptrdiff_t j;
    for (j = 0; begin != end; ++begin, ++j)
    {
        for (ptrdiff_t n = 1; n <= j && j % (n * 2) == 0; n *= 2)
        { std::inplace_merge(begin - n * 2, begin - n, begin); }
    }
    --j;
    for (ptrdiff_t m = 1, n = 1; n <= j; n *= 2)
    {
        if (j & n)
        {
            std::inplace_merge(begin - (m + n), begin - m, begin);
            m += n;
        }
    }
    return begin;
}

Answer 3

Here is C# version of bottom-up-mergesort (for some more details you may refer to my blog @ http://dream-e-r.blogspot.com/2014/07/mergesort-arrays-and-lists.html)

void BottomUpMergesort(int[] a)
        {
            int[] temp = new int[a.Length];
            for (int runWidth = 1; runWidth < a.Length; runWidth = 2 * runWidth)
            {
                for (int eachRunStart = 0; eachRunStart < a.Length; 
                    eachRunStart = eachRunStart + 2 * runWidth)
                {
                    int start = eachRunStart;
                    int mid = eachRunStart + (runWidth - 1);
                    if(mid >= a.Length)
                    {
                        mid = a.Length - 1;
                    }
                    int end = eachRunStart + ((2 * runWidth) - 1);
                    if(end >= a.Length)
                    {
                        end = a.Length - 1;
                    }

                    this.Merge(a, start, mid, end, temp);
                }
                for (int i = 0; i < a.Length; i++)
                {
                    a[i] = temp[i];
                }
            }

And merge is defined as:

void Merge(int[] a, int start, int mid, int end, int[] temp)
        {
            int i = start, j = mid+1, k = start;
            while((i<=mid) && (j<=end))
            {
                if(a[i] <= a[j])
                {
                    temp[k] = a[i];
                    i++;
                }
                else
                {
                    temp[k] = a[j];
                    j++;
                }
                k++;
            }
            while(i<=mid)
            {
                temp[k] = a[i];
                i++;
                k++;
            }
            while (j <= end)
            {
                temp[k] = a[j];
                j++;
                k++;
            }
            Assert.IsTrue(k == end+1);
            Assert.IsTrue(i == mid+1);
            Assert.IsTrue(j == end+1);
        }

        }

Just for reference here is the TopDownMergesort:

void TopDownMergesort(int[] a, int[] temp, int start, int end)
        {
            if(start==end)
            {
                //run size of '1'
                return;
            }
            int mid = (start + end) / 2;
            this.TopDownMergesort(a, temp, start, mid);
            this.TopDownMergesort(a, temp, mid + 1, end);
            this.Merge(a, start, mid, end, temp);
            for(int i = start;i<=end;i++)
            {
                a[i] = temp[i];
            }
        }

UnitTests

[TestMethod]
        public void BottomUpMergesortTests()
        {
            int[] a = { 13, 4, 1, 3, 8, 11, 9, 10 };
            this.BottomUpMergesort(a);
            int[] b = { 1, 3, 4, 8, 9, 10, 11, 13 };
            Assert.IsTrue(a.Length == b.Length);
            for (int i = 0; i < a.Length; i++)
            {
                Assert.IsTrue(a[i] == b[i]);
            }
            List<int> l = new List<int>();
            for (int i = 10; i >= 1; i--)
            {
                l.Add(i);
            }
            var la = l.ToArray();
            this.BottomUpMergesort(la);
            for (int i = 1; i <= 10; i++)
            {
                Assert.IsTrue(la[i - 1] == i);
            }
            l.Clear();
            for (int i = 16; i >= 1; i--)
            {
                l.Add(i);
            }
            la = l.ToArray();
            this.BottomUpMergesort(la);
            for (int i = 1; i <= l.Count; i++)
            {
                Assert.IsTrue(la[i - 1] == i);
            }
        }

Answer 4

Here is the Java Implementation

public static <T extends Comparable<? super T>> void iterativeMergeSort(T[] seed) {

    for (int i = 1; i <seed.length; i=i+i)
    {
        for (int j = 0; j < seed.length - i; j = j + i+i)
        {
            inPlaceMerge(seed, j, j + i-1, Math.min(j+i + i -1, seed.length -1));
        }
    }       
}
public static <T extends Comparable<? super T>>  void inPlaceMerge(T[] collection, int low, int mid, int high) {
    int left = low;
    int right = mid + 1;

    if(collection[mid].equals(collection[right])) {
        return ;//Skip the merge if required
    }
    while (left <= mid && right <= high) {          
        // Select from left:  no change, just advance left
        if (collection[left].compareTo(collection[right]) <= 0) {
            left ++;
        } else { // Select from right:  rotate [left..right] and correct
            T tmp = collection[right]; // Will move to [left]
            rotateRight(collection, left, right - left);
            collection[left] = tmp;
            // EVERYTHING has moved up by one
            left ++; right ++; mid ++;
        }
    }       
}

Here is the Unit Test private Integer[] seed;

@Before
public void doBeforeEachTestCase() {
    this.seed = new Integer[]{4,2,3,1,5,8,7,6};
}
@Test
public void iterativeMergeSortFirstTest() {
    ArrayUtils.<Integer>iterativeMergeSort(seed);
    Integer[] result = new Integer[]{1,2,3,4,5,6,7,8};
    assertThat(seed, equalTo(result));  
}