Merging two sorted Arraylists into one sorted Arraylist

Question

My code should merge two already sorted arraylists into one sorted arraylist and if one of the arraylists used is not sorted then it should return null.

public class MergeSorted {
public static void merge(ArrayList<Integer> a, ArrayList<Integer> b) {

    for (int i = 0, j = 0; j < b.size(); i++) {
        if (i == a.size() || a.get(i) > a.get(j)) {
            a.add(i, b.get(j++));
        }
    }
}  
}

This is what I attempted but can't get the idea of returning null if they are not equal, Im new to java and this is my second week so please be patient with me. I know I should have an if statement checking if they are sorted and an else but what should I include inside the if?

First, only call that method if you already know both lists are sorted (separate problems to resolve ;)) Second, if you have the appropiated `equals()` and `compare()` you could order the result list using `Collections.sort()` — Fran Montero, Aug 05 '15 at 10:00
I suppose returning `null` implies that you should be creating new array list to store merged result, not modifying source array list. — Vladimir, Aug 05 '15 at 10:01
`it should return null` First of all you are not returning anything i.e. void. — Naman Gala, Aug 05 '15 at 10:02
If by "sorted" you mean numerical order, then you could simply create a `TreeSet` and insert the contents of both lists there. Using a `Set` merges the data for you so that duplicates are removed. Or do you want to keep duplicate entries? — Mick Mnemonic, Aug 05 '15 at 10:02
Is that a homework task? I cannot image why someone want to return null in case the list is already sorted. — AlexWien, Aug 05 '15 at 10:04
@Mick I think this is an exercise in writing the "merge" part of the merge sort algorithm, which works on unsorted data structures. — ttzn, Aug 05 '15 at 10:04

score 1 · Answer 1 · edited May 31 '23 at 19:19

Please refer to this link for comparing if the List implementation is equal. Please note that the ArrayList implementation of yours contains List<Integer> and thus the sorting takes place in the natural order. In case of equal return true or else false. You can change it as required to return any flag.

Sort and compare 2 lists if equal - List of String

There are useful Apache Common library classes available, which can help you in merging the array lists that are sorted : This will give you what you are looking for. org.apache.commons.collections4 package. Apache Common Lib version 4 - collate()

eg., List<Integer> mergedList = CollectionUtils.collate(list1, list2);

score 1 · Answer 2 · answered Aug 05 '15 at 10:31

Problem

Check if the two lists are sorted, if they are then it will merge the two lists into a single sorted list, whereas if the lists are not sorted return null.

Code Solution:

Try the following code:

public class MergeSorted {
public static List merge(List<Integer> aList, List<Integer> bList) {

    List mergeList = new ArrayList<Integer>();

    //checking if list 'A' is sorted
    List temp = new ArrayList(aList);
    Collections.sort(temp);
    boolean aSorted = temp.equals(aList);

    //checking if list 'B' is sorted
    temp = new ArrayList(bList);
    Collections.sort(temp);
    boolean bSorted = temp.equals(bList);

    //if both lists are sorted then merge them
    if(true == aSorted && true == bSorted) {
        mergeList.addAll(aList);
        mergeList.addAll(bList);
        Collections.sort(mergeList);
    }

   return mergeList; 
    }
  }

Hello, can't i use my code with something added for the check? — Jonathon K, Aug 05 '15 at 14:16
i cant use collections.sort or any of this. Also the output has to be an ArrayList and the inputs ArrayLists not lists. — Jonathon K, Aug 05 '15 at 14:33
@JonathonK you can use ArrayList instead of List it's upto you, however List is a better option. The above code is complete and you use it as it is. — Karan Sharma, Aug 06 '15 at 07:08

score 0 · Answer 3 · answered Aug 05 '15 at 10:21

The generic way is something like this:

public class MergeSort {

    public static <T extends Comparable<? super T>> List<T> merge(List<T> a, List<T> b) {
        if (!isSorted(a) || !isSorted(b)) {
            return null;
        }

        final List<T> result = new ArrayList<T>(a.size() + b.size());
        result.addAll(a);
        result.addAll(b);

        Collections.sort(result);

        return result;
    }

    private static <T extends Comparable<? super T>> boolean isSorted(final List<T> list) {
        T prevItem = null;
        for (T item : list) {

            if (prevItem != null && item.compareTo(prevItem) < 0) {
                return false;
            }

            prevItem = item;
        }

        return true;
    }

}

You can easily replace all these generic Ts with Integer if you only need it for them...

Merging two sorted Arraylists into one sorted Arraylist

3 Answers3