Merge Sort Iterative Implementation - Not working

Question

I have the below merge sort iterative implementation, but somehow, it is not working. I debugged it, but couldn't find the cause.

Merge'ing function would remain the same as the recursive case, only the array dividing logic would be different, if I'm correct.

Please rectify, if I'm going in wrong direction.

Answer 1

I think you have a problem when you try to use the same object to represent different intervals: At MergeSort_Iterative loop , when you are adding new elements to list1 you are using "info" object as temporal variable and then you add it to list1 collection.

In Java, all object variables are references so when you add the object to the collection you are not adding a copy of it but a reference which is being modified and inserted again.

info.left = left;
info.right = mid;
list1.add(info);

info.left = mid + 1;
info.right = right;
list1.add(info);

To fix that you should create two objects in order two perform the inserctions:

info = new MergePosInfo();
info.left = left;
info.right = mid;
list1.add(info);

info = new MergePosInfo();
info.left = mid + 1;
info.right = right;
list1.add(info);

On the other hand, once the problem described above is solved, you should iterate over list2 from shorter to wider intervals and from left to right positions and your algorithm is not generating list2 in that order.

You need to modify MergeSort_Iterative:

public static void MergeSort_Iterative(int[] numbers, int left, int right) {
    int mid;
    if (right <= left)
        return;

    LinkedList<MergePosInfo> list1 = new LinkedList<MergePosInfo>();
    LinkedList<MergePosInfo> list2 = new LinkedList<MergePosInfo>();

    for(int i = left; i <= right; i+=2)
    {
        MergePosInfo info = new MergePosInfo();
        info.left = i;
        info.right = (i+1<=right)?(i+1):i;
        info.mid = -1;
        list1.add(info);
        list2.add(info);
    }

    int l = right-left+1;
    for(int partsSize = 2; partsSize <= l/2; partsSize*=2)
    {
        int ll1 =    list1.size();
        for(int i = 0; i < ll1; i+=2)
        {
            MergePosInfo info2 = new MergePosInfo();
            info2.left = list1.get(0).left;
            info2.right = list1.get(1).right;
            info2.mid = (info2.left+info2.right)/2;

            list1.remove(0);
            list1.remove(0);

            list1.add(info2);
            list2.addLast(info2);
        }
    }


    for (int i = 0; i < list2.size(); i++) {
        System.out.println("Merge [" + Integer.toString(list2.get(i).left) + " , "  + Integer.toString(list2.get(i).right) + "]" );
        DoMerge(numbers, list2.get(i).left, list2.get(i).mid+1,
                list2.get(i).right);
    }

}

As well as to add some lines to DoMerge:

public static void DoMerge(int[] numbers, int left, int mid, int right) {
       int[] temp = new int[25];
       int i, left_end, num_elements, tmp_pos;

       left_end = (mid - 1);
       tmp_pos = left;
       num_elements = (right - left + 1);

       if(num_elements == 2)
       {
           if(numbers[left]>numbers[right])
           {
               int buffer = numbers[left];
               numbers[left] = numbers[right];
               numbers[right] = buffer;
           }
           return;
        }
       ...

As you can see the solution I provided only works when "numbers" length is 2^k. You can try to fix it by yourself and if you can't I will give you the last change.

I left System.out.println("Merge [" + Integer.toString(list2.get(i).left) + " , " + Integer.toString(list2.get(i).right) + "]" );

line so you can understand how merge sort works.

Answer 2

            info.left = left;
            info.right = mid;
            list1.add(info);

            info.left = mid + 1;
            info.right = right;
            list1.add(info);

You are operating on the same object. Use a different object for each iteration, the same way you are doing with info2