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

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:

• Considering the way I coded it, does it still have the same efficiency?

• Did I do this in an acceptable way? If not, why?

Main:

Random rand = new Random();
    ArrayList array = new ArrayList();
    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 ar = new ArrayList();
int loBound = 0, hiBound = 1;
public Algorithm(ArrayList 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 left = new ArrayList();
ArrayList right = new ArrayList();
// 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 partitionSize){
loBound = hiBound;
hiBound = loBound + partitionSize;
}else {
loBound = hiBound;
hiBound = ar.size();
}
}
// updates original ArrayList after sorting 'left' and 'right'
private void update(ArrayList left, ArrayList right, int loInd, int hiInd){
// sort
ArrayList result = new ArrayList();
int lIndex = 0, rIndex = 0, resIndex = 0;
while (lIndex < left.size() || rIndex < right.size()){
if (lIndex < left.size() && rIndex < right.size()){
i

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.

StackExchange Code Review Q#40585, answer score: 4