Is this non-recursive mergesort efficient and a good way to simulate the recursive version?

Question

My teacher assigned us to do the recursive version of mergesort, yet I heard that the non-recursive version (bottom up) is a bit tougher, so I decided to this one as well. My main concerns are:

1. Considering the way I coded it, does it still have the same efficiency?
2. Did I do this in an acceptable way? If not, why?

Main:

    Random rand = new Random();
    ArrayList<Integer> array = new ArrayList<Integer>();
    for (int i = 0; i < 100; i++){
        array.add(rand.nextInt(20));
    }
    System.out.println("Original:");
    for (int num: array){
        System.out.print(" " + num);
    }
    Algorithm algo = new Algorithm(array);
    algo.print();

Code:

ArrayList<Integer> ar = new ArrayList<Integer>();
int loBound = 0, hiBound = 1;
public Algorithm(ArrayList<Integer> initAr){
    ar = initAr;
    partition();
}
public void partition(){
    if (ar.size() > 1){
        int partitionSize = 1;
        int arraySize = ar.size();

        if (ar.size() % 2 != 0) // if the size is odd make it even so loop doesn't terminate early without sorting all values
            arraySize++;

        while (arraySize / 2 >= partitionSize){
            while (true){
                ArrayList<Integer> left = new ArrayList<Integer>();
                ArrayList<Integer> right = new ArrayList<Integer>();
                // Variables which will be sent to 'update' method as parameters. Tells method which indexes to update (in-between low and high)
                int loInd = loBound, hiInd;
                for (int i = loBound; i < hiBound; i++){
                    left.add(ar.get(i));
                }
                calcBounds(partitionSize);
                for (int j = loBound; j < hiBound; j++){
                    right.add(ar.get(j));
                }
                hiInd = hiBound;
                if (right.size() != partitionSize){
                    update(left, right, loInd, hiInd);
                    break;
                }
                update(left, right, loInd, hiInd);
                calcBounds(partitionSize);
            }
            partitionSize*=2;
            loBound = 0;
            hiBound = partitionSize;
        }
    }
}
// calculates the indexes from which I will extract from the original array
private void calcBounds(int partitionSize){
    if (ar.size() - hiBound > partitionSize){
        loBound = hiBound;
        hiBound = loBound + partitionSize;
    }else {
        loBound = hiBound;
        hiBound = ar.size();
    }
}
// updates original ArrayList after sorting 'left' and 'right'
private void update(ArrayList<Integer> left, ArrayList<Integer> right, int loInd, int hiInd){
    // sort
    ArrayList<Integer> result = new ArrayList<Integer>();
    int lIndex = 0, rIndex = 0, resIndex = 0;
    while (lIndex < left.size() || rIndex < right.size()){
        if (lIndex < left.size() && rIndex < right.size()){
            if (left.get(lIndex) <= right.get(rIndex)){
                result.add(resIndex, left.get(lIndex));
                resIndex++;
                lIndex++;
            }else {
                result.add(resIndex, right.get(rIndex));
                resIndex++;
                rIndex++;
            }
        }else if (lIndex < left.size()){
            result.add(resIndex, left.get(lIndex));
            resIndex++;
            lIndex++;
        }else if (rIndex < right.size()){
            result.add(resIndex, right.get(rIndex));
            resIndex++;
            rIndex++;
        }
    }
    // update original ArrayList using result ArrayList
    int count = 0;
    for (int i = loInd; i < hiInd; i ++){
        ar.set(i, result.get(count));
        count++;
    }
}

void print(){
    System.out.println();
    System.out.println("Sorted:");
    for (int num: ar){
        System.out.print(" " + num);
    }
}

Answer 1

I have not looked into it too deeply to be able to fully answer your first question. Althought for you to get a picture of efficiency I would suggest to take the normal recursive merge sort and time it using System.nanoTime() and compare it with this version on the same array to be sorted. That could give you a picture about time complexity and regarding memory you would have to use a profiler. Simply jconsole can be enough in this case to see the memory consumption - careful with the GC kicking in when you don't want it.

Second question: I am not saying that it would be a bad looking code but I have difficulties to understand it. I would suggest few improvements that can help the readability. For example the first one in the method partition - instead of having the whole code block in if (ar.size() > 1) I would suggest having if (ar.size() <= 1) then do return. This gets rid of one level of curly braces for the rest of the code block.

Another suggestion would be to use instance variable as least as possible, in this case loBound = 0, hiBound = 1 and ar. There is a "Brook's law for methods" that says that method should be passed necessary variables as parameters if possible, if not then accessing instance variables and so on. Besides it is some statement it is also improves readability if the method changes only parameters it got passed and not instance variables. You can better track what is being changed and returned in and from the method.

From where I am sitting the main downside of this code would be to come to it half year later and figure out what it does and if it does it right. I would say even the author of the code would have to take some time to figure it out.

I am sorry I might not help you with your first question. Hope the comments on the second one regarding the code style could be of use for you.

Answer 2

First off, the practical performance difference between the iterative and recursive versions is likely to be modest in terms of time, but the former will save you O(n log n) procedure calls.

Secondly, for performance, you shouldn't be creating new array-lists on every iteration. You only need one extra array for working space. Personally, I find an array based implementation easier to understand.

Here's my effort in C#:

void Main()
{
    var xs = new int[] { 1, 3, 5, 1, 2, 4 };
    MergeSort(xs);
    Console.WriteLine(xs);
}

// In-place merge-sort.
static void MergeSort(int[] xs)
{
    var n = xs.Length;
    var src = xs;
    var tgt = new int[n];
    for (var span = 1; span < n; span += span) {
        for (var a = 0; a < n; a += span + span) {
            var b = Math.Min(n, a + span);
            var c = Math.Min(n, b + span);
            Merge(src, tgt, a, b, c);
        }
        var tmp = src;
        src = tgt;
        tgt = tmp;
    }
    if (xs != src) for (var i = 0; i < n; i++) xs[i] = src[i];
}

// Merge the ordered subarrays src[a..b) and src[b..c) into tgt[a..c).
// src and tgt must be distinct arrays.
static void Merge(int[] src, int[] tgt, int a, int b, int c)
{
    var aTop = b;
    var bTop = c;
    var i = a;
    while (a < aTop || b < bTop) {
        tgt[i++] = (a == aTop) ? src[b++] : (b == bTop) ? src[a++] : (src[a] <= src[b]) ? src[a++] : src[b++];
    }
}