title: Using Merge Sort on ArrayList and LinkedList : Java
body: <p>I need to sort a list of 1000 ints with a merge sort; from what I can tell, my algorithm looks like it should work, but when I print out the 'sorted' list, it's still not sorted. I'm really stumped, and I was wondering if anybody could point me in the right direction. Here's my code:</p>
  
  <pre><code>package edu.neumont.csc250;
  
  import java.util.Random;
  
  import edu.neumont.csc250.LinkedList.Node;
  
  
  public class Tester {
  
      ArrayList&lt;Integer&gt; arrayList1000;
      ArrayList&lt;Integer&gt; arrayList10000;
      ArrayList&lt;Integer&gt; arrayList100000;
  
      LinkedList&lt;Integer&gt; linkedList1000;
      LinkedList&lt;Integer&gt; linkedList10000;
      LinkedList&lt;Integer&gt; linkedList100000;
  
      public Tester(){}
  
      public void createLists(){
          arrayList1000 = new ArrayList&lt;Integer&gt;();
          arrayList1000 = populateRandoms(arrayList1000, 1000);
          arrayList10000 = new ArrayList&lt;Integer&gt;();
          arrayList10000 = populateRandoms(arrayList10000, 10000);
          arrayList100000 = new ArrayList&lt;Integer&gt;();
          arrayList100000 = populateRandoms(arrayList100000, 100000);
  
          linkedList1000 = new LinkedList&lt;Integer&gt;();
          linkedList1000 = populateRandoms(linkedList1000, 1000);
          linkedList10000 = new LinkedList&lt;Integer&gt;();
          linkedList10000 = populateRandoms(linkedList10000, 10000);
          linkedList100000 = new LinkedList&lt;Integer&gt;();
          linkedList100000 = populateRandoms(linkedList100000, 100000);
      }
  
      public ArrayList&lt;Integer&gt; populateRandoms(ArrayList&lt;Integer&gt; list, int size){
          Random r = new Random();
  
          for(int i = 0; i &lt; size; i++){
              list.add(r.nextInt(1000) + 1);
              //System.out.println(list.get(i));
          }
          return list;
      }
  
      public LinkedList&lt;Integer&gt; populateRandoms(LinkedList&lt;Integer&gt; list, int size){
          Random r = new Random();
  
          for(int i = 0; i &lt; size; i++){
              list.add(r.nextInt(1000) + 1);
              //System.out.println(list.get(i));
          }
          return list;
      }
  
      public void arraySearches(){
          System.out.println("STARTING SEARCH OF 1000 INTEGERS...");
  
          long startTime = System.nanoTime();
          long endTime;
          try {
              System.out.println(sequentialSearch(arrayList1000, 123));
              if(sequentialSearch(arrayList1000, 123) == -1){
                  System.out.println("Not found in the list.");
              }
              else{
                  //System.out.println(arrayList1000.get(sequentialSearch(arrayList1000, 123)));
              }
          } finally {
              endTime = System.nanoTime();
              long duration = endTime - startTime;
              System.out.println("1000 elements takes " + (duration/1000000000) + " seconds, " +
                  (duration%1000000000)/1000000+ " milliseconds, " + (duration%1000000000)%1000000 +
                  " nanoseconds to search a CustomArrayList with a sequential search.");
          }
  
  
          System.out.println("STARTING SEARCH OF 10000 INTEGERS...");
  
          long startTime2 = System.nanoTime();
          long endTime2;
          try {
              System.out.println(sequentialSearch(arrayList10000, 123));
              if(sequentialSearch(arrayList10000, 123) == -1){
                  System.out.println("Not found in the list.");
              }
              else{
                  //System.out.println(arrayList10000.get(sequentialSearch(arrayList10000, 123)));
              }
          } finally {
              endTime2 = System.nanoTime();
              long duration2 = endTime2 - startTime2;
              System.out.println("10000 elements takes " + (duration2/1000000000) + " seconds, " +
                  (duration2%1000000000)/1000000+ " milliseconds, " + (duration2%1000000000)%1000000 +
                  " nanoseconds to search a CustomArrayList with a sequential search.");
          }
  
  
          System.out.println("STARTING SEARCH OF 100000 INTEGERS...");
  
          long startTime3 = System.nanoTime();
          long endTime3;
          try {
              System.out.println(sequentialSearch(arrayList100000, 123));
              if(sequentialSearch(arrayList100000, 123) == -1){
                  System.out.println("Not found in the list.");
              }
              else{
                  //System.out.println(arrayList100000.get(sequentialSearch(arrayList100000, 123)));
              }
          } finally {
            endTime3 = System.nanoTime();
              long duration3 = endTime3 - startTime3;
              System.out.println("100000 elements takes " + (duration3/1000000000) + " seconds, " +
                  (duration3%1000000000)/1000000+ " milliseconds, " + (duration3%1000000000)%1000000 +
                  " nanoseconds to search a CustomArrayList with a sequential search.");
          }
      }
  
      public void linkedSearches(){
          System.out.println("STARTING SEARCH OF 1000 INTEGERS...");
  
          long startTime = System.nanoTime();
          long endTime;
          try{
              System.out.println(sequentialSearch(linkedList1000, 123));
              if(sequentialSearch(linkedList1000, 123) == -1){
                  System.out.println("Not found in the list.");
              }
              else{
                  //System.out.println(linkedList1000.get(sequentialSearch(linkedList1000, 123)));
              }
          } finally {
              endTime = System.nanoTime();
              long duration = endTime - startTime;
              System.out.println("1000 elements takes " + (duration/1000000000) + " seconds, " +
                  (duration%1000000000)/1000000+ " milliseconds, " + (duration%1000000000)%1000000 +
                  " nanoseconds to search a CustomLinkedList with a sequential search.");
          }
  
  
          System.out.println("STARTING SEARCH OF 10000 INTEGERS...");
  
          long startTime2 = System.nanoTime();
          long endTime2;
          try{
              System.out.println(sequentialSearch(linkedList10000, 123));
              if(sequentialSearch(linkedList10000, 123) == -1){
                  System.out.println("Not found in the list.");
              }
              else{
                  //System.out.println(linkedList10000.get(sequentialSearch(linkedList10000, 123)));
              }
          } finally {
              endTime2 = System.nanoTime();
              long duration2 = endTime2 - startTime2;
              System.out.println("10000 elements takes " + (duration2/1000000000) + " seconds, " +
                  (duration2%1000000000)/1000000+ " milliseconds, " + (duration2%1000000000)%1000000 +
                  " nanoseconds to search a CustomLinkedList with a sequential search.");
          }
  
  
          System.out.println("STARTING SEARCH OF 100000 INTEGERS...");
  
          long startTime3 = System.nanoTime();
          long endTime3;
          try{
              System.out.println(sequentialSearch(linkedList100000, 123));
              if(sequentialSearch(linkedList100000, 123) == -1){
                  System.out.println("Not found in the list.");
              }
              else{
                  //System.out.println(linkedList100000.get(sequentialSearch(linkedList100000, 123)));
              }
          } finally {
              endTime3 = System.nanoTime();
              long duration3 = endTime3 - startTime3;
              System.out.println("100000 elements takes " + (duration3/1000000000) + " seconds, " +
                  (duration3%1000000000)/1000000+ " milliseconds, " + (duration3%1000000000)%1000000 +
                  " nanoseconds to search a CustomLinkedList with a sequential search.");
          }
      }
  
      public void arraySorts(){
          arrayList1000 = mergeSort(arrayList1000);
          for(int i = 0; i&lt;1000; i++){
              System.out.println(arrayList1000.get(i));
          }
      }
  
      public void linkedSorts(){
  //      linkedList1000 = mergeSort(linkedList1000);
  //      for(int i = 0; i&lt;1000; i++){
  //          System.out.println(arrayList1000.get(i));
  //      }
      }
  
      public ArrayList&lt;Integer&gt; mergeSort(ArrayList&lt;Integer&gt; list){
          ArrayList&lt;Integer&gt; first = new ArrayList&lt;Integer&gt;();
          ArrayList&lt;Integer&gt; second = new ArrayList&lt;Integer&gt;();
          ArrayList&lt;Integer&gt; sortedList = null;
  
          System.out.println("MERGE SORTING...");
          if(list.size() &gt; 1){
              for(int i = 0; i&lt;(list.size()/2); i++){
                  first.add(list.get(i));
              }
              for(int j = list.size()/2; j&lt;list.size(); j++){
                  second.add(list.get(j));
              }
              mergeSort(first);
              mergeSort(second);
          }
          sortedList = merge(first, second);
  
  
          return sortedList;
      }
  
      public ArrayList&lt;Integer&gt; merge(ArrayList&lt;Integer&gt; first, ArrayList&lt;Integer&gt; second){
          ArrayList&lt;Integer&gt; newList = new ArrayList&lt;Integer&gt;();
  
          int i = 0;
          int j = 0;
  
          while(i&lt;first.size() &amp;&amp; j&lt;second.size()){
              if(first.get(i) &lt;= second.get(j)){
                  newList.add(first.get(i));
                  i++;
              }
              else{
                  newList.add(second.get(j));
                  j++;
              }
          }
          if(i==first.size()){
              for(int k = j; k&lt;second.size(); k++){
                  newList.add(second.get(k));
              }
          }
          else{
              for(int l = i; l&lt;first.size(); l++){
                  newList.add(first.get(l));
              }
          }
  //      while(i&lt;first.size()){
  //          for(int i : first){
  //              
  //          }
  //          newList.add()
  //      }
  //      while(j&lt;second.size()){
  //          
  //      }
  
          return newList;
      }
  
      public List&lt;Integer&gt; mergeSort(LinkedList&lt;Integer&gt; list){
          return list;
      }
  
      public int sequentialSearch(ArrayList&lt;Integer&gt; list, int key){
          for(int i = 0; i &lt; list.size()-1; i++){
              if(list.get(i).equals(key)){
                  return i;
              }
          }
          return -1;
      }
  
      public int sequentialSearch(LinkedList&lt;Integer&gt; list, int key){
          Node current = list.head;
          for(int i = 0; i &lt; list.size()-1; i++){
              if(current.content.equals(key)){
                  return i;
              }
          }
          return -1;
      }
  
      public static void main(String[] args){
          Tester t = new Tester();
          t.createLists();
          //t.arraySearches();
          //t.linkedSearches();
          t.arraySorts();
          //t.linkedSorts();
      }
  }
  </code></pre>