Java Recursive MergeSort for ArrayLists

Question

I have been having a problem with my mergesort function, as I am not able to sort a series of integers or strings whenever inputting it into the program. I have an outside class that calls items into it, however it simply doesn't sort the numbers/strings. The two methods are below, I don't know where the problem is. Numbers are randomly inputted.

CODE:

/**
     * Takes in entire vector, but will merge the following sections together:
     * Left sublist from a[first]..a[mid], right sublist from a[mid+1]..a[last].
     * Precondition: each sublist is already in ascending order
     *
     * @param a
     *            reference to an array of integers to be sorted
     * @param first
     *            starting index of range of values to be sorted
     * @param mid
     *            midpoint index of range of values to be sorted
     * @param last
     *            last index of range of values to be sorted
     */
    private void merge(ArrayList<Comparable> a, int first, int mid, int last) {
        int x;
        int i;
        ArrayList<Comparable> left = new ArrayList<Comparable>();
        ArrayList<Comparable> right = new ArrayList<Comparable>();
        mergeSort(a,first,mid);
        for(i = 0; i < a.size() - mid; i++){
            left.add(i,a.get(i));
            a.remove(i);
        }
        mergeSort(a,mid,last);
        for (x = mid; x < a.size(); x++) {
            right.add(x,a.get(x));
            a.remove(x);
        }
        if ((left.get(i).compareTo(right.get(x))) > 0) {
            i++;
            a.add(i);
        } else if (i < x) {
            x++;
            a.add(x);
        }


        System.out.println();
        System.out.println("Merge");
        System.out.println();

    }

    /**
     * Recursive mergesort of an array of integers
     *
     * @param a
     *            reference to an array of integers to be sorted
     * @param first
     *            starting index of range of values to be sorted
     * @param last
     *            ending index of range of values to be sorted
     */
    public void mergeSort(ArrayList<Comparable> a, int first, int last) {

        int mid = (first + last)/2;
        if(first == last){

        }else if(last - first == 1){
            merge(a,first, mid ,last);              
        }else{
            last = mid;
        }


                }

Solution 1

I have an outside class that calls items into it, however it simply doesn't sort the numbers/strings. The two methods are below, I don't know where the problem is.

The first problem is that if you call your mergeSort method with first = 0 and last = a.size() you won't sort anything as you only call merge if last-first == 1 :

public void mergeSort(ArrayList<Comparable> a, int first, int last) {
    int mid = (first + last)/2;
    if(first == last){
    }else if(last - first == 1){
        // you only merge if last - first == 1...
        merge(a,first, mid ,last);              
    }else{
        last = mid;
    }
}

Appart from this point, I don't get how you're trying to implement the Merge Sort algorithm. It's neither a top down, nor a bottom up implementation. You're splitting inside the merge method which is also really odd. It would have been easier to help you if you had provided your pseudo code + the way you call your public method. IMHO you have a real issue with your algorithm.

In fact the merge sort algorithm is really simple to implement. To illustrate this, I wrote this top down implementation of the merge sort algorithm using Deque instead of List objects:

import java.util.Deque;
import java.util.LinkedList;

public class Example {

    private LinkedList<Comparable> merge(final Deque<Comparable> left, final Deque<Comparable> right) {
        final LinkedList<Comparable> merged = new LinkedList<>();
        while (!left.isEmpty() && !right.isEmpty()) {
            if (left.peek().compareTo(right.peek()) <= 0) {
                merged.add(left.pop());
            } else {
                merged.add(right.pop());
            }
        }
        merged.addAll(left);
        merged.addAll(right);
        return merged;
    }

    public void mergeSort(final LinkedList<Comparable> input) {
        if (input.size() != 1) {
            final LinkedList<Comparable> left = new LinkedList<Comparable>();
            final LinkedList<Comparable> right = new LinkedList<Comparable>();
            // boolean used to decide if we put elements
            // in left or right LinkedList
            boolean logicalSwitch = true;
            while (!input.isEmpty()) {
                if (logicalSwitch) {
                    left.add(input.pop());
                } else {
                    right.add(input.pop());
                }
                logicalSwitch = !logicalSwitch;
            }
            mergeSort(left);
            mergeSort(right);
            input.addAll(merge(left, right));
        }
    }
}

I used Deque because peek()/ pop() is ways prettier IMHO than get(0) and remove(0) but it's up to you. If you absolutely want to use ArrayList here follows the corresponding implementation.

import java.util.ArrayList;
import java.util.List;

public class Example {

    private List<Comparable> merge(final List<Comparable> left, final List<Comparable> right) {
        final List<Comparable> merged = new ArrayList<>();
        while (!left.isEmpty() && !right.isEmpty()) {
            if (left.get(0).compareTo(right.get(0)) <= 0) {
                merged.add(left.remove(0));
            } else {
                merged.add(right.remove(0));
            }
        }
        merged.addAll(left);
        merged.addAll(right);
        return merged;
    }

    public void mergeSort(final List<Comparable> input) {
        if (input.size() != 1) {
            final List<Comparable> left = new ArrayList<Comparable>();
            final List<Comparable> right = new ArrayList<Comparable>();
            boolean logicalSwitch = true;
            while (!input.isEmpty()) {
                if (logicalSwitch) {
                    left.add(input.remove(0));
                } else {
                    right.add(input.remove(0));
                }
                logicalSwitch = !logicalSwitch;
            }
            mergeSort(left);
            mergeSort(right);
            input.addAll(merge(left, right));
        }
    }
}

Both implementation work with Integerand String or other Comparable.

Hope it helps.

Solution 2

There are several problems but an important one is that you should not iterate over a list while modifying the list, i.e. in:

for (i = 0; i < a.size() - mid; i++){
    left.add(i,a.get(i));
    a.remove(i);
}

because once you remove an element, indexes for others are not the same... So you add in left elements of a that are not what you think.

A working code is the following (with some comments) :

 private static void merge(ArrayList<Comparable> a) {
    if (a.size()<=1) return; // small list don't need to be merged

    // SEPARATE

    int mid = a.size()/2; // estimate half the size

    ArrayList<Comparable> left = new ArrayList<Comparable>();
    ArrayList<Comparable> right = new ArrayList<Comparable>();

    for(int i = 0; i < mid; i++) left.add(a.remove(0)); // put first half part in left
    while (a.size()!=0) right.add(a.remove(0)); // put the remainings in right
    // Here a is now empty

    // MERGE PARTS INDEPENDANTLY

    merge(left);  // merge the left part
    merge(right); // merge the right part

    // MERGE PARTS

    // while there is something in the two lists
    while (left.size()!=0 && right.size()!=0) {
      // compare both heads, add the lesser into the result and remove it from its list
      if (left.get(0).compareTo(right.get(0))<0) a.add(left.remove(0));
      else                                       a.add(right.remove(0));
    }

    // fill the result with what remains in left OR right (both can't contains elements)
    while(left.size()!=0)  a.add(left.remove(0));
    while(right.size()!=0) a.add(right.remove(0));
  }

It has been tested on some inputs... Example:

[4, 7, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11]
[0, 1, 1, 2, 3, 4, 4, 5, 6, 7, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

For efficiency you may use subList method to avoid constructing too much sub lists explicitly, it will need to take care about indices.

Solution 3

A WARNING about Kraal's implementation that got the checkmark. It's a great implementation, but Kraal's Merge sort doesn't preserve the relative order of items that have the same value, which in some cases, when sorting objects for instance, is an important strength that merge sort has that other sorting algorithms, like quicksort, do not have. I modified Kraal's code to preserve relative orders.

private static List<Object> merge(final List<Object> left, final List<Object> right) {
            printArr("left", left);
            printArr("Right", right);
            final List<Object> merged = new ArrayList<>();
            while (!left.isEmpty() && !right.isEmpty()) {
                if(left.get(0).getValue()-right.get(0).getValue() <= 0){
                    merged.add(left.remove(0));
                } else {
                    merged.add(right.remove(0));
                }
            }
            merged.addAll(left);
            merged.addAll(right);
            return merged;
     }

 public static void mergeSort(final List<Object> input) {
     if (input.size() > 1) {
         final List<Object> left = new ArrayList<Object>();
         final List<Object> right = new ArrayList<Object>();
         boolean logicalSwitch = true;

         while (!input.isEmpty()) {
             if (logicalSwitch) {
                 left.add(input.remove(0));
             } else {
                 right.add(input.remove(input.size()/2));
             }
             logicalSwitch = !logicalSwitch;
         }
         mergeSort(left);
         mergeSort(right);
         input.addAll(merge(left, right));
     }
 }

Solution 4

If you want to sort an array using Merge sort, and not to implement a sorting algorithm by yourself, I recommend using standard Java sorting algorithms because it implements "Merge sort" algorithm for non primitive types.

Collections.sort();

If you would like to implement your own version of Merge sort then you should look first at this implementation.

And if you are interested in better understanding sorting algorithms I recommend this book.

View more solutions

Comments

[guillaume girod-vitouchkina]

advice: begin with little quantity of numbers to sort, trace at some strategic steps, and iterate.

[ahll]

Read wiki en.wikipedia.org/wiki/Merge_sort, I think it is very clear.

[Admin]

This is really good! however I needed help with how to create it with Arraylists instead of deque as I haven't covered that in my class yet

[Admin]

Thanks! This really helps

[Kraal]

Well the second part of the answer makes use of ArrayLists. What was missing ?

[Admin]

oh sorry, I missed the second part of the code, now it seems much more helpful

[Kingsley]

Please explain how this code solves the OP's question.