Merge sort in JAVA : Top-down implementation using lists

// Comment Merge Sort for array

 public static void mergeSort(int[] A) {
  if (A == null)
   throw new NullPointerException("Input doesn't exist.");

  int len = A.length;

  if (len == 0)
   throw new IllegalArgumentException("No input from user.");

  mergeSortUtil(A, 0, len - 1);
 }

 private static void mergeSortUtil(int[] a, int l, int r) {

  if (l >= r)
   return;

  int m = l + (r - l) / 2;

  mergeSortUtil(a, l, m);
  mergeSortUtil(a, m + 1, r);

  merge(a, l, m, r);

 }

 private static void merge(int[] a, int l, int m, int r) {

  int k = 0, i, j;
  int[] b = new int[(r - l) + 1];

  for (i = l, j = m + 1; i <= m && j <= r;) {
   if (a[i] < a[j])
    b[k++] = a[i++];
   else
    b[k++] = a[j++];
  }

  while (i <= m)
   b[k++] = a[i++];

  while (j <= r)
   b[k++] = a[j++];

  for (int s = l, f = 0; f < b.length; s++) {
   a[s] = b[f++];
  }
 }

Top-down implementation using lists :

function merge_sort(list m)
    // Base case. A list of zero or one elements is sorted, by definition.
    if length(m) <= 1
        return m

    // Recursive case. First, *divide* the list into equal-sized sublists.
    var list left, right
    var integer middle = length(m) / 2
    for each x in m before middle
         add x to left
    for each x in m after or equal middle
         add x to right

    // Recursively sort both sublists.
    left = merge_sort(left)
    right = merge_sort(right)
    // *Conquer*: merge the now-sorted sublists.
    return merge(left, right)

In this example, the merge function merges the left and right sublists.

function merge(left, right)
    var list result
    // assign the element of the sublists to 'result' variable until there is no element to merge. 
    while length(left) > 0 or length(right) > 0
        if length(left) > 0 and length(right) > 0
           // compare the first two element, which is the small one, of each two sublists.
            if first(left) <= first(right)
                append first(left) to result
                left = rest(left)
            else
                append first(right) to result
                right = rest(right)
        else if length(left) > 0
            append first(left) to result
            left = rest(left)
        else if length(right) > 0
            append first(right) to result
            right = rest(right)
    end while
    return result

 public static LNode mergeSortList(LNode list) {
  int len = length(list);
  if (len <= 1)
   return list;

  LNode left = list, right = null;

  right = addLeftList(left, len);

  left = mergeSortList(left);
  right = mergeSortList(right);
  LNode res = merge(left, right);

  return res;
 }

 private static int length(LNode list) {
  int len = 0;
  for (LNode curr = list; curr != null; curr = curr.next)
   len++;
  return len;
 }

 private static LNode addLeftList(LNode list, int n) {
  int m = n / 2;
  LNode curr = list;
  for (int i = 0; curr != null && i < m - 1; i++)
   curr = curr.next;
  list = curr.next;
  curr.next = null;
  return list;
 }

 private static LNode merge(LNode left, LNode right) {
  LNode result = null, curr = null, tmp = null;
  while (left != null && right != null) {
   if (left.val < right.val) {
    curr = left;
    left = left.next;
   } else {
    curr = right;
    right = right.next;
   }

   if (result == null) {
    result = curr;
    tmp = curr;
   } else {
    tmp.next = curr;
    tmp = tmp.next;
   }
  }

  if (left != null)
   tmp.next = left;
  if (right != null)
   tmp.next = right;

  return result;
 }