How do I sort two ArrayList, while merging into one?

Question

I have two ArrayList's, for example:

ArrayList a = new ArrayList();
    a.add(10);
    a.add(35);
    a.add(51);

ArrayList b = new ArrayList();
    b.add(24);
    b.add(46);
    b.add(81);

I need to create a function, which puts elements from B to A in a sorted query. (In my mind it must check elements on the same positions in A and B and put 24 between 10 and 35, 46 between 35 and 51, and the last one is 81). I have:

 public static void merge(ArrayList a, ArrayList b)
 {
     a.addAll(b);
     Collections.sort(a);
 }

But it is not an efficient algorithm (N^2). Is there a more efficient one?

Also, don't use *raw types*.. Provide a type parameter for the type — Thiyagu, Aug 02 '18 at 08:33
How, as a newbie, do you care about the effectiveness of the sorting algorithm? :-) As long as your arrays do not contain thousands of elements, the sorting will be instantanious anyways. — Ridcully, Aug 02 '18 at 08:34
Looks like your two lists are sorted? If they are, checkout merge sort, that is O(N) — zhh, Aug 02 '18 at 08:36
@Ridcully, yes, i care because i already have 'dirty' method, but i want to do it better ^_^. That's why i'm here for help. — Anton Pozharitskiy, Aug 02 '18 at 08:46
I wouldn't call the Collections.sort() method 'dirty' per se. If you have a look at this question, it appears, that they use MergeSort, if possible. https://stackoverflow.com/questions/2883821/java-collections-sort-performance — Ridcully, Aug 02 '18 at 08:48

score 1 · Answer 1 · answered Aug 02 '18 at 09:03

From the documentation of List.sort

This implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons. Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays.

The complexity for this implementation is O(n lg(n)). Most of the time even lower, especially if the input is almost sorted. Complexity might change between Java versions, but O(n lg(n)) is pretty solid.

Back to your algorithmn, we can say that

a.addAll(b); // requires O(n)
Collections.sort(a); // requires O(n lg(n))

So it won`t ever be worse than O(n lg(n)).

score 0 · Answer 2 · answered Aug 02 '18 at 08:47

As you said those two lists are sorted, then there is a O(N) way to merge those two lists.

static List<Integer> merge(List<Integer> a, List<Integer> b) {
    List<Integer> merged = new ArrayList<>(a.size() + b.size());
    int ai = 0, bi = 0;
    while (ai < a.size() && bi < b.size()) {
        if (a.get(ai) < b.get(bi))
            merged.add(a.get(ai++));
        else
            merged.add(b.get(bi++));
    }
    while (ai < a.size())
        merged.add(a.get(ai++));
    while (bi < b.size())
        merged.add(b.get(bi++));
    return merged;
}

How do I sort two ArrayList, while merging into one?

2 Answers2