How to merge 2 Arraylists in to 1 that is alphabetically sorted

Question

I have been trying to merge two string arraylists that are already alphabetically sorted, into 1 big one that also turns out to be alphabetically sorted. It is preferred that this is done using one loop but two are fine too. Also the comapreTo method must be used to compare the Strings. This is what I have but it doesn't work. It might be better for you to just start over as this is probably not very well wrtitten.

public static ArrayList<String> merge(ArrayList<String> al1, ArrayList<String> al2){
     ArrayList<String> result = new ArrayList<String>();

     int longLength = al1.size() > al2.size() ? al1.size():al2.size();

            for(int i=0;i<longLength;i++){
            if(al1.size() > i && al2.size() > i && al1.get(i).compareTo(al2.get(i)) >= 0){
            result.add(al2.get(i));
            } 
            else if(al1.size() > i && al2.size() > i && al1.get(i).compareTo(al2.get(i)) < 0) {
            result.add(al1.get(i));
            } 
            else if(al1.size() > i && al2.size() <= i) {
            result.add(al1.get(i));
            } 
            else if(al1.size() <= i && al2.size() > i) {
            result.add(al2.get(i));
            }
        }
     return result;
  }

Assignments like this are not a really good fit for stackoverflow. Because they are tailored in a way to teach **you** something specific. In this case obviously manually merging lists with iteration and using the compareTo method. However most experiences java programmers will neither use a loop nor manually call the compareTo method to merga and sort two lists into one. So you will get answers that are 100% correct but will most likely not help you pass your course. — OH GOD SPIDERS, Mar 02 '17 at 16:56
"It might be better for you to just start over". The "do my homework for me" posts are becoming more helpful and sophisticated. — Kayaman, Mar 02 '17 at 17:06
and http://stackoverflow.com/questions/13069605/merge-two-arraylist-lists-in-list1-while-it-remain-sorted — Petter Friberg, Mar 03 '17 at 11:57

Haifeng Zhang · Answer 1 · 2017-03-02T17:02:35.397

Use addAll() to add all elements of list2 to list1, and then sort them using utility class Collections

addAll() appends all the elements of list2 to the end of list1.
Collections.sort() sorts the specified list into ascending order, according to the natural ordering of its elements

Example:

public class Main {
    public static void main(String[] args) {
        List<String> list1 = new ArrayList<>();
        list1.add("a");
        list1.add("c");

        List<String> list2 = new ArrayList<>();
        list2.add("b");

        list1.addAll(list2);// the order is "a" "c" "b" now
        Collections.sort(list1);

        for(String e: list1){
            System.out.println(e);
        }
    }
}

Output:

a
b
c

You should note that the solution is suboptimal in terms of runtime. — Ivaylo Toskov, Mar 02 '17 at 17:02

score 1 · Answer 2 · answered Mar 02 '17 at 17:38

Just keep grabbing elements at the beginning of the each list and add them to the sorted list. When any of the lists are out of elements just add add all elements of the other list.

Example code. Please note that list.remove(0) is O(n) for ArrayList and popping can be done by keeping two index variables instead. I leave that up to you to complete your homework!

List<String> result = new ArrayList<>(list1.size() + list2.size());
while( !list1.isEmpty() && !list2.isEmpty()){
    if( list1.get(0).compareTo(list2.get(0)) < 0){
        result.add(list1.remove(0));
    } else {
        result.add(list2.remove(0));
    }
}

if( list1.isEmpty()){
    result.addAll(list2);
} else{
    result.addAll(list1);
}

How to merge 2 Arraylists in to 1 that is alphabetically sorted

2 Answers2