How to merge two ordered list of objects?

Question

public  class ListMerge
{
   public static void main( String[] args) 
   {

      Scanner input = new Scanner(System.in);

      System.out.println ("Input length of arraylist 1:");
      int n = input.nextInt();
      ArrayList x = new ArrayList();
      ArrayList y = new ArrayList();
      for (int i = 0; i < n; i++)
      {
        System.out.println ("Input x[ " + i +"] :" );
         x.add(new Integer(i));

      }


      System.out.println ("Input length of arraylist 2:");
      int m = input.nextInt();


      for (int i = 0; i < m; i++)
      {
        System.out.println ("Input y[ " + i +"] :" );
        y.add(new Integer(i));

      }
      List<Integer> all = new ArrayList<Integer>();

      all.addAll(x);
      all.addAll(y);
      System.out.println(all);


  }
}

I did this but its not taking values from user. pls tell me why....

By ordered you mean sorted? You need to merge two sorted lists into one sorted list? — polygenelubricants, Jun 16 '10 at 11:10

score 5 · Answer 1 · edited Mar 04 '13 at 13:04

5

Directly from wikipedia:

function merge(left,right)
    var list result
    while length(left) > 0 and length(right) > 0
        if first(left) ≤ first(right)
            append first(left) to result
            left = rest(left)
        else
            append first(right) to result
            right = rest(right)
    end while
    if length(left) > 0 
        append left to result
    else  
        append right to result
    return result

edited Mar 04 '13 at 13:04

instanceof me

38,520
3
31
40

answered Jun 16 '10 at 08:14

unbeli

29,501
5
55
57

That's a mergesort. He just wants to merge the lists, i.e. "append left to result, append right to result, return result". – Matt Mitchell Jun 16 '10 at 08:16
2

That's part of mergesort, of course. He needs to merge two ordered lists, I guess, keeping it ordered. This is exactly what this step of mergesort does – unbeli Jun 16 '10 at 08:18
He mentioned nothing about order in his original question though. I was just pointing out that if he can't work out how to join two lists there's no way he's going to understand mergesort. – Matt Mitchell Jun 17 '10 at 02:24

score 1 · Answer 2 · answered May 28 '14 at 15:21

1

With Google Guava:

Iterable<Integer> all = 
    Iterables.mergeSorted(ImmutableList.of(x, y), Ordering.natural());
System.out.println(all);

answered May 28 '14 at 15:21

palacsint

28,416
10
82
109

score 0 · Answer 3 · edited May 23 '17 at 12:01

To complete the circle of knowledge, here's an implementation of @unbeli's / Wikipedia's answers.

public List<T> mergeOrdered(final List<T> list0, final List<T> list1) {
    List<T> result = new ArrayList<T>();

    while (list0.size() > 0 && list1.size() > 0) {
    if (list0.get(0).compareTo(list1.get(0)) < 0) {
            result.add(list0.get(0));
            list0.remove(0);
        }
        else {
            result.add(list1.get(0));
            list1.remove(0);
        }
    }

    if (list0.size() > 0) {
        result.addAll(list0);
    }
    else if (list1.size() > 0) {
        result.addAll(list1);
    }

    return result;
}

Note that lists created using Arrays.asList() will result in a fixed length array from which elements cannot be removed - so make sure you're passing dynamic lists!

public List<T> buildDynamicListFromArray(final T[] arr0) {
    List<T> result = new ArrayList<T>();
    int len = arr0.length;
    for (int i = 0; i < len; i++) {
        result.add(arr0[i]);
    }
    return result;
}

score 0 · Answer 4 · answered Mar 15 '14 at 19:38

Here is an implementation using potentially more efficient iterators, pre-alloc of result arraylist, custom comparator, and no side effects on input list:

public static <T, C extends Comparator<T>> List<T> mergeOrderedAscending( List<T> list0,  List<T> list1, C c)
{
    if(list0 == null || list1 == null || c == null)
        throw new IllegalArgumentException("null parameter");

    Iterator<T> it0 = list0.iterator();
    Iterator<T> it1 = list1.iterator();

    List<T> result = new ArrayList<T>(list0.size() + list1.size());


    T i0 = null;
    T i1 = null;


    if(it0.hasNext())
        i0 = it0.next();
    else
        i0 = null;


    if(it1.hasNext())
        i1 = it1.next();
    else
        i1 = null;

    while (i0 != null && i1 != null) {

        if (c.compare(i0, i1) < 0) {
            result.add(i0);

            if(it0.hasNext())
                i0 = it0.next();
            else
                i0 = null;

        }
        else {
            result.add(i1);

            if(it1.hasNext())
                i1 = it1.next();
            else
                i1 = null;
        }
    } 


    if (i0 != null) {

        do {
            result.add(i0);

            if(it0.hasNext())
                i0 = it0.next();
            else
                i0 = null;
        } while(i0 != null);
    }
    else if (i1 != null) {
        do {
            result.add(i1);

            if(it1.hasNext())
                i1 = it1.next();
            else
                i1 = null;
        } while(i1 != null);
    }

    return result;
}

How to merge two ordered list of objects?

4 Answers4

Linked