merge sort implementation with arraylisr<String> not sorting

Question

I am trying to implement a mergeSort function to sort an ArrayList of words that I got from input.txt. (I use the DeleteStopWords() method for this.

The sorted ArrayList that is being returned does not sort properly however I cannot understand why.

Below are my mergSort and merge methods.

public static ArrayList<String> mergeSort(ArrayList<String> listofWords) {

    ArrayList<String> sorted = new ArrayList<String> ();

    if (listofWords.size() == 1) {
        sorted = listofWords;
    } else {
        int middle = listofWords.size() / 2;

        ArrayList<String> leftSide = new ArrayList<String> ();
        ArrayList<String> rightSide = new ArrayList<String> ();

        for (int x = 0; x<middle; x++) {
            leftSide.add(listofWords.get(x));
        }

        for (int x = 0; x<middle; x++) {
            rightSide.add(listofWords.get(x));
        }

        mergeSort(leftSide);
        mergeSort(rightSide);
        sorted = merge(leftSide, rightSide);
    }
    return sorted;
}

public static ArrayList<String> merge(ArrayList<String> leftSide, ArrayList<String> rightSide) {

    ArrayList<String> Sortedarray = new ArrayList<String> ();

    int index = 0;
    int leftIndex = 0;
    int rightIndex = 0;

    while (leftIndex<leftSide.size() && rightIndex<rightSide.size()) {

        if ((leftSide.get(leftIndex)).compareTo(rightSide.get(rightIndex))<0) {
            Sortedarray.add(leftSide.get(leftIndex));
            leftIndex++;
        } else {
            Sortedarray.add(rightSide.get(rightIndex));
            rightIndex++;
        }

        index++;
    }

    while (leftIndex<leftSide.size()) {
        Sortedarray.add(leftSide.get(leftIndex));
        leftIndex++;
        index++;
    }

    while (rightIndex<rightSide.size()) {
        Sortedarray.add(rightSide.get(rightIndex));
        rightIndex++;
        index++;
    }

    return Sortedarray;
}

When you run this with a debugger, what is the first thing it does wrong? — Scott Hunter
– Scott Hunter, Commented May 7, 2022 at 15:42
Your mergeSort method is returning the sorted result in a different list. When calling recursively, you are ignoring the returned partial result. The problem is here: mergeSort(leftSide); and in the following line. I trust you to fix it yourself. — Anonymous
– Anonymous, Commented May 7, 2022 at 16:48

dani-vta · Accepted Answer · 2022-05-07 17:19:20Z

There are a couple of problems in your code:

Firstly, in how you split your lists. Both of them retrieve only the first half of the parameter list. The first for should get the first middle elements, while the second the rest of them.
Secondly, your merge method accepts two lists and returns a new instance which is never assigned to anything in your mergeSort method.

Your code should look like this:

public static ArrayList<String> mergeSort(ArrayList<String> listofWords) {
    //If the list contains only one element there's nothing to sort
    if (listofWords.size() == 1) {
        return listofWords;
    }

    //Computing the middle index to split the list
    int middle = listofWords.size() / 2;
    ArrayList<String> leftSide = new ArrayList<>();
    ArrayList<String> rightSide = new ArrayList<>();

    //Adding to the left list the first half
    for (int x = 0; x < middle; x++) {
        leftSide.add(listofWords.get(x));
    }

    //Adding to the right list the second half (the x index should start from where you left)
    for (int x = middle; x < listofWords.size(); x++) {
        rightSide.add(listofWords.get(x));
    }

    //Retrieving the lists and then returning their merge
    leftSide = mergeSort(leftSide);
    rightSide = mergeSort(rightSide);
    return merge(leftSide, rightSide);
}

public static ArrayList<String> merge(ArrayList<String> leftSide, ArrayList<String> rightSide) {
    ArrayList<String> sortedList = new ArrayList<>();
    int leftIndex = 0;
    int rightIndex = 0;

    //Merging the sorted lists into one sorted list
    while (leftIndex < leftSide.size() && rightIndex < rightSide.size()) {
        if (leftSide.get(leftIndex).compareTo(rightSide.get(rightIndex)) < 0) {
            sortedList.add(leftSide.get(leftIndex));
            leftIndex++;
        } else {
            sortedList.add(rightSide.get(rightIndex));
            rightIndex++;
        }
    }

    //Adding the remanining elements from the left list
    while (leftIndex < leftSide.size()) {
        sortedList.add(leftSide.get(leftIndex));
        leftIndex++;
    }

    //Adding the remanining elements from the right list
    while (rightIndex < rightSide.size()) {
        sortedList.add(rightSide.get(rightIndex));
        rightIndex++;
    }

    return sortedList;
}

Collectives™ on Stack Overflow

merge sort implementation with arraylisr<String> not sorting

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related