Java merge sort on strings only works on arraylist up to four elements

Question

I'm trying to use merge sort to alphabetically sort a list of words inputted from the command prompt. It works when I sort an arraylists up to a size of 4 words, but when I try using five or more words: it returns the array in the wrong order or in the same order it originally was in.

When I debugged it I realized that it sorts correctly all the way up until it comes to merging the last two halves. Ex. if its an arraylist of size 7, it sorts correctly the words in positions 0 - 4 and the words in positions 5 - 7 but merges them in the wrong order.

Due to this, I believe the error is in the mergeSort function, since the merge function is working considering it was able to sort the smaller arrays correctly. However, I don't see how there can be an error there since it just divides the array in half and calls other functions.

Comparing it to other mergesort functions I found online and on here, the code is very similar so I'm having a hard time seeing my mistake.

The inputting words from the cmd and calling mergesort is below:

    public static void main(String[] args) {
        List<String> List = new ArrayList<String>();
        Scanner input = new Scanner(System.in); 
        while(input.hasNextLine()){ 
            String word = input.nextLine().trim();
            if (word.equals("")) break;
            List.add(word); 
        }
        input.close();
        System.out.println("unsorted: " + ListA);
        mergeSort(List, 0, List.size()-1);
        System.out.println("sorted: " + ListA);
    }

My mergeSort function and merge function are these:

    public static void mergeSort(List<String> wordArray, int lower, int upper) {
        if ((upper-lower) >= 1 ) {//if arraylist size is greater than 1
            int halfPt = (upper + lower)/2; //dividing the arraylist
            int s1 = lower;
            int f1 = halfPt;
            int s2 = halfPt +1;
            int f2 = upper;
            mergeSort(wordArray, s1, f1); //mergesort on first half
            mergeSort(wordArray, s2, f2); //mergesort on second half
            merge(wordArray, s1, f1, s2, f2); //merge first and second half
        }
    }

    public static void merge(List<String> wordArray, int s1, int f1, int s2, int f2) {
        List<String> finalArray = new ArrayList<String>();
        while (s1<=f1 && s2<=f2) { //alphabetically sorting both half arrays
            if(wordArray.get(s1).compareTo(wordArray.get(s2))<0) {//placing smallest element first
                finalArray.add(wordArray.get(s1));
                s1++;
            } else {
                finalArray.add(wordArray.get(s2));
                s2++;
            }
        }
        //add leftovers in half-arraylists
        while (s1 <= f1) {
            finalArray.add(wordArray.get(s1));
            s1++;
        }   
        while (s2 <= f2) {
            finalArray.add(wordArray.get(s2));
            s2++;
        }
        for (int i = 0; i < wordArray.size(); i++) { //copy sorted array into original array
            if (wordArray.size()!=finalArray.size()) break;
            wordArray.set(i, finalArray.get(i));
        }
    }

Where could I be going wrong? Any help is very much appreciated, and thank you in advance!

mightyWOZ · Accepted Answer · 2020-03-01 08:39:27Z

1

Your problem lies in the last for loop of merge method.

for (int i = 0; i < wordArray.size(); i++) { //copy sorted array into original array
      // This if is source of problem, size of your final array will only match that of
      // wordArray in the last call to merge.
      // In all the other invocations it will not match, hence the copying never occurs in those cases
      if (wordArray.size()!=finalArray.size()) break;
      wordArray.set(i, finalArray.get(i));
}

To fix it modify the last for loop as follows.

// In the beggining of merge method store values of s1 and f2
// so that we know the start and end index of the merge operation
int start = s1;
int end = f2;

// Now modify the last for loop as
for(int i=0; i<finalArray.size() && start <= end; i++, start++){
   wordArray.set(start, finalArray.get(i));
}

answered Mar 1, 2020 at 8:39

mightyWOZ

8,4453 gold badges35 silver badges51 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Java merge sort on strings only works on arraylist up to four elements

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