public class MergeSort{
  /*Basic idea:
    1. Divide the unsorted list into n sublists, each containing 1 element
    2. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining.
  */
  //I want it to work for a LinkedList, so I'm going to include the listNode class too.


  public static ListNode sortList(ListNode head) {
    //Base case: If it's only one element, just return that element
    if ( head == null || head.next == null ){ return head; }
    //Otherwise, cut it in half, sort the first half, sort the second half, and then merge them
    else{
      //Cut it in half and sort the halves
      //Merge them
      ListNode rightHalf = sortList(splitNode(head));
      ListNode leftHalf = sortList(head);
      return merge(leftHalf, rightHalf);
    }
  }

  public static int getSize(ListNode head) {
    int i=1;
    while (head.next != null){ i++; head = head.next;}
    return i;
  }

  public static ListNode splitNode(ListNode head){
    int halfSize = getSize(head)/2;
    ListNode middleNode = head;
    ListNode middleNodePre = head;
    for(int i=0; i<halfSize; i++){
      middleNode = middleNode.next;
      if(i < halfSize-1){ middleNodePre = middleNode; }
    }
    middleNodePre.next = null;
    return middleNode;
  }

  public static ListNode merge(ListNode a, ListNode b){
    /*I need to rethink how I'm merging my lists since I think this is the problem.
      -First we're given two sorted lists, e.g. a = [-5, 0, 2] and b = [-3, -2, 1, 8]
      -At any point in the merge process, the next element to be added can only be either the next active element from a, or the next active element from b.
      -So we need a way to keep track of this "active" element for each list.  I was trying to do this by maintaining a counter but I think it's better to use the attributes of the LinkedList data type for this.
      -We don't need to make a new result list; we can use the existing lists
    */
    int totalSize = getSize(a) + getSize(b);
    if (totalSize == 0) { return null; }
    else if (a == null){ return b; }
    else if (b == null){ return a; }
    else{
      ListNode result;
    }
  }

  public static void add(ListNode a, int val){
    ListNode currentNode = a;
    while (currentNode.next != null){
      currentNode = currentNode.next;
    }
    currentNode.next = new ListNode(val);
  }

}


@@ -1059,43 +1059,8 @@
 ad;%0A
-    ListNode middleNodePre = head;%0A
     
@@ -1082,16 +1082,18 @@
 halfSize
+-1
 ; i++)%7B%0A
@@ -1136,43 +1136,29 @@
     
-  if(i %3C halfSize-1)%7B middle
+%7D%0A    List
 Node
-P
+ 
 re
+sult
  = m
@@ -1170,17 +1170,14 @@
 Node
-; %7D%0A    %7D
+.next;
 %0A   
@@ -1191,11 +1191,8 @@
 Node
-Pre
 .nex
@@ -1212,26 +1212,22 @@
  return 
-middleNode
+result
 ;%0A  %7D%0A%0A 
@@ -1914,72 +1914,34 @@
    i
-nt totalSize = getSize(a) + getSize(b);%0A    if (totalSize == 0) 
+f (a == null && b == null)
 %7B re
@@ -2062,226 +2062,956 @@
 sult
-;%0A    %7D%0A  %7D%0A%0A  public static void add(ListNode a, int val)%7B%0A    ListNode currentNode = a;%0A    while (currentNode.next != null)%7B%0A      currentNode = currentNode.next;%0A    %7D%0A    currentNode.next = new ListNode(val);%0A  %7D%0A
+ = new ListNode(500);%0A      int totalSize = getSize(a) + getSize(b);%0A      for(int i=0; i%3CtotalSize; i++)%7B%0A        System.out.println(%22AAA%22);%0A        add(result, getSmaller(a, b).val);%0A        System.out.println%0A        if (a.val %3C b.val)%7B a = a.next; %7D%0A        else %7B b = b.next; %7D%0A      %7D%0A      return result.next;%0A    %7D%0A  %7D%0A%0A  public static void add(ListNode a, int val)%7B%0A    ListNode currentNode = a;%0A    while (currentNode.next != null)%7B%0A      currentNode = currentNode.next;%0A    %7D%0A    currentNode.next = new ListNode(val);%0A  %7D%0A%0A  public static ListNode getSmaller(ListNode a, ListNode b)%7B%0A    ListNode result = null;%0A    if (a.val %3C b.val) %7B result = a; %7D%0A    else %7B result = b; %7D%0A    return result;%0A  %7D%0A%0A  public static String printList(ListNode head)%7B%0A    int size = MergeSort.getSize(head);%0A    String result = %22%5B%22;%0A    for(int i=0; i%3Csize; i++)%7B%0A      result += head.val + %22, %22;%0A      head = head.next;%0A    %7D%0A    return result += %22%5D%22;%0A  %7D
 %0A%7D%0A%0A

Update MergeSort