Merge Sort with ArrayList in Java

Question

I am trying to merge these ArrayLists. list3 is the final one. Everything is working fine, but the last number ,400, wont show up in the final array. I have no clue why or what to do. I'm trying to get the ArrayList's sorted and I'm almost done except for that last number that wont show up.

import java.util.ArrayList;
public class TextLab12st
{
    public static void main(String args[])
{
    int jsaList1[] = {101, 105, 115, 125, 145, 165, 175, 185, 195, 225, 235, 275, 305, 315, 325, 335, 345, 355, 375, 385};
    int jsaList2[] = {110, 120, 130, 140, 150, 160, 170, 180, 190, 200, 210, 220, 230, 240, 250, 270, 280, 320, 350, 400};

    Array list1 = new Array(jsaList1,"List #1");
    Array list2 = new Array(jsaList2,"List #2");
    Array list3 = new Array("Merged List");

    list3.merge(list1,list2,list3);

    list1.display();
    list2.display();
    list3.display();

}

}

class Array
{
private ArrayList<Integer> list;
private int size;
private String listName;

public Array(String ln)
{
    list = new ArrayList<Integer>();
    size = 0;
    listName = ln;
}

public Array(int[] jsArray, String ln)
{
    list = new ArrayList<Integer>();
    size = jsArray.length;
    listName = ln;
    for (int j = 0; j < size; j++)
        list.add( new Integer( jsArray[j] ));
}

public void display ()
{
    System.out.println("\n" + listName + ":\n");
    System.out.println(list + "\n");
}

public void merge(Array that, Array theOther, Array result)
{
    {
        // Merge both halves into the result array
        // Next element to consider in the first array
        int iFirst = 0;
        // Next element to consider in the second array
        int iSecond = 0;

        // Next open position in the result
        int j = 0;
        // As long as neither iFirst nor iSecond is past the end, move the
        // smaller element into the result.
        while (iFirst < that.size && iSecond < theOther.size) 
        {
            if (that.list.get(iFirst) < theOther.list.get(iSecond)) 
            {
                result.list.add(that.list.get(iFirst));
                iFirst++;
            } 
            else 
            {
                result.list.add(theOther.list.get(iSecond));
                iSecond++;
            }
            j++;
        }

    }

}

}

what's wrong with collections.sort()?

hd1
– hd1

2014-03-06 17:09:47 +00:00
Commented Mar 6, 2014 at 17:09 — hd1
– hd1, Commented Mar 6, 2014 at 17:09

radai · Accepted Answer · 2014-03-06 17:10:17Z

4

after the loop that runs over both arrays:

    while (iFirst < that.size && iSecond < theOther.size) 
    {
        if (that.list.get(iFirst) < theOther.list.get(iSecond)) 
        {
            result.list.add(that.list.get(iFirst));
            iFirst++;
        } 
        else 
        {
            result.list.add(theOther.list.get(iSecond));
            iSecond++;
        }
        j++;
    }

you need to see if there's anything remaining in one of the arrays after you've reached the end of the other:

if (iFirst < that,size) {
   //copy everything remaining in that to output
} else if (iSecond < theOther.size) {
   //copy everything from theOther to output
}

answered Mar 6, 2014 at 17:10

radai

24.3k10 gold badges76 silver badges118 bronze badges

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

1 Comment

ima_mango Over a year ago

Thanks, I had no clue. How exactly do I copy everything though?

user3360944 · Accepted Answer · 2014-03-06 17:10:36Z

1

// this condition stops when you reach the end of either list
// you need to continue until you reach the end of both lists
 while (iFirst < that.size && iSecond < theOther.size)

answered Mar 6, 2014 at 17:10

user3360944

5584 silver badges11 bronze badges

Collectives™ on Stack Overflow

Merge Sort with ArrayList in Java

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related