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
– Fran Montero, Commented Aug 5, 2015 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
– Vladimir, Commented Aug 5, 2015 at 10:01
it should return null First of all you are not returning anything i.e. void. — Naman Gala
– Naman Gala, Commented Aug 5, 2015 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
– Mick Mnemonic, Commented Aug 5, 2015 at 10:02
@Mick I think this is an exercise in writing the "merge" part of the merge sort algorithm, which works on unsorted data structures. — ttzn
– ttzn, Commented Aug 5, 2015 at 10:04

Karan Sharma · Accepted Answer · 2015-08-05 10:31:25Z

1

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; 
    }
  }

answered Aug 5, 2015 at 10:31

Karan Sharma

2,6875 gold badges34 silver badges49 bronze badges

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

3 Comments

Jonathon K Over a year ago

Hello, can't i use my code with something added for the check?

Jonathon K Over a year ago

i cant use collections.sort or any of this. Also the output has to be an ArrayList and the inputs ArrayLists not lists.

Karan Sharma Over a year ago

@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.

Pat Lee · Accepted Answer · 2023-05-31 19:19:12Z

1

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);

edited May 31, 2023 at 19:19

Pat Lee

1,6881 gold badge12 silver badges15 bronze badges

answered Aug 5, 2015 at 10:27

Karthik R

5,8162 gold badges23 silver badges32 bronze badges

Comments

FlasH from Ru · Accepted Answer · 2015-08-05 10:21:04Z

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...

Collectives™ on Stack Overflow

Merging two sorted Arraylists into one sorted Arraylist

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related