using merge sort for string sorting from text file

Question

I am going to write a code for sorting string from text file by mergesort method.

if (l.get(0) <= r.get(0))

at this part appearing a redline. I know it is only for primitive, I tried to use compareTo but can't finish it properly.

enter image description here

private static ArrayList<String> mergeSort(ArrayList<String> lines) {
        if (lines.size() <= 1) {
            return lines;
        }
        ArrayList<String> left = new ArrayList<String>();
        ArrayList<String> right = new ArrayList<String>();
        for (String x : lines) {
            if (lines.indexOf(x) < (lines.size()) / 2)
                left.add(x);
            else {
                right.add(x);
            }
        }
        left = mergeSort(left);
        right = mergeSort(right);
        return merge(left, right);
    }

    private static ArrayList<String> merge(ArrayList<String> l, ArrayList<String> r) {
        ArrayList<String> result = new ArrayList<String>();
        while (l.size() > 0 && r.size() > 0) {
            if (l.get(0) <= r.get(0)) {
                result.add(l.get(0));
                l.remove(0);
            }
            else {
                result.add(r.get(0));
                r.remove(0);
            }
        }
        while (l.size() > 0) {
            result.add(l.get(0));
            l.remove(0);
        }
        while (r.size() > 0) {
            result.add(r.get(0));
            r.remove(0);
        }
        return result;
    }

Answer 1

String.compareTo()

The Java String class compareTo() method compares the given string with the current string lexicographically. It returns a positive number, negative number, or 0. It compares strings on the basis of the Unicode value of each character in the strings. If the first string is lexicographically greater than the second string, it returns a positive number (difference of character value). If the first string is less than the second string lexicographically, it returns a negative number, and if the first string is lexicographically equal to the second string, it returns 0.

Note:
if string1 > string2, it returns positive number

if string1 < string2, it returns negative number

if string1 == string2, it returns 0

qutoes from gfg.

use compareTo method of String because java doesn't support < & > operators for strings comparisions.

 while (l.size() > 0 && r.size() > 0) {
            if (l.get(0).compareTo(r.get(0))<=0) {
                result.add(l.get(0));
                l.remove(0);
            }
            else {
                result.add(r.get(0));
                r.remove(0);
            }
        }

You are getting SO Excepetion because of indexOf if suppose list has {"A", "A", "C", "A"} then indexOf("A") will return 0 ever time you call it.

if (lines.indexOf(x) < (lines.size()) / 2)
                left.add(x);
            else {
                right.add(x);
            }

code

import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Arrays;


public class MergeSort{
        final static PrintStream out = System.out;


        private static ArrayList<String> mergeSort(ArrayList<String> lines) {
                if (lines.size() <= 1) {
                        return lines;
                }
                ArrayList<String> left = new ArrayList<String>(lines.subList(0, lines.size()/2));
                ArrayList<String> right = new ArrayList<String>(lines.subList(lines.size()/2, lines.size()));

                /*for (String x : lines) {
                        if (lines.indexOf(x) < (lines.size()) / 2)
                                left.add(x);
                        else {
                                right.add(x);
                        }
                }*/
                /*for(int i =0 ;i<lines.size()/2;i++)
                        left.add(lines.get(i));
                for(int i = lines.size()/2;i<lines.size();i++)
                        right.add(lines.get(i));*/
                left = mergeSort(left);
                right = mergeSort(right);
                return merge(left, right);
        }

        private static ArrayList<String> merge(ArrayList<String> l, ArrayList<String> r) {
                ArrayList<String> result = new ArrayList<String>();
                while (l.size() > 0 && r.size() > 0) {
                        if (l.get(0).compareTo(r.get(0)) <= 0) {
                                result.add(l.get(0));
                                l.remove(0);
                        }
                        else {
                                result.add(r.get(0));
                                r.remove(0);
                        }
                }
                while (l.size() > 0) {
                        result.add(l.get(0));
                        l.remove(0);
                }
                while (r.size() > 0) {
                        result.add(r.get(0));
                        r.remove(0);
                }
                return result;
        }
        //Main
        public static void main(String ... $){
                out.println(mergeSort(new ArrayList<>(Arrays.asList("G", "P",
                                                        "A", "A", "O"))));
        }
}

Output:

$ javac MergeSort.java  && java MergeSort
[A, A, G, O, P]