Sort
by Isai Damier

/***************************************************************************
 * Author: Isai Damier
 * Title: Singly Linked List
 * Project: geekviewpoint
 * Package: datastructure
 *
 * Description: A LinkedList is a data structure that allows access
 *   to a collection of data using pointers/references. While an
 *   array can also be defined as above, LinkedLists and arrays differ
 *   in how they are stored in memory and in the operations they
 *   allow. Unlike an array that must be stored in a block of memory,
 *   the nodes of a LinkedList can be stored anywhere because each
 *   node has a reference to the node that succeeds it. Because the
 *   nodes are stored so loosely, inserting nodes into a LinkedList
 *   is easy; whereas in an array, all the succeeding elements must
 *   be shifted. Of course, insertion also means changing the size of
 *   the array, which means creating the entire array anew.
 *
 *   Perhaps the greatest beauty of LinkedList is that it allows
 *   accessing an entire sequence of nodes using only one variable:
 *   a reference to the first node in the sequence.
 *
 *   Countless operations can be performed on LinkedLists. Following
 *   are a few, ranging from the common to the very interesting.
 **************************************************************************/ 
 public class SinglyLinkedList {

  Node head = null;
  Node tail = null;

 /*****************************************************************
   * Time Complexity of Solution:
   *   O(n*log n).
   *
   * Description: Sort the elements in this linked list in ascending
   *   order.
   *
   * Technical Details: Sorting a LinkedList in place is very costly:
   *   in the order of O(n^2 * log(n)) with a good algorithm.
   *   Therefore it makes sense to create an array from the list,
   *   sort the array, and then empty the array into the list by
   *   index. It's kind of like: unbutton a shirt; move the buttons
   *   around; then button the shirt anew. (I think it's a good analogy.)
   *****************************************************************/
  public void sort() {
    if (2 > this.size()) {
      return;
    }

    int[] A = new int[this.size()];
    //unfasten the buttons (i.e. unbutton the shirt)
    int x = 0;
    for (Node t = head; null != t; t = t.next) {
      A[x++] = t.data;//list fills array
    }    //sort the buttons
    mergesort(A, 0, A.length - 1);
    //refasten the buttons (i.e. button the shirt anew)
    x = 0;
    for (Node t = head; null != t; t = t.next) {
      t.data = A[x++];//array fills list
    }
  }

  private void mergesort(int[] input, int first, int last) {
    //break array into smaller structurally identical pieces
    int mid = (first + last) / 2;
    if (first < last) {
      mergesort(input, first, mid);
      mergesort(input, mid + 1, last);
    }
    //merge sorted pieces to get solution to original array
    int a = 0, f = first, l = mid + 1;
    int[] tmp = new int[last - first + 1];

    while (f <= mid && l <= last) {
      tmp[a++] = input[f] < input[l] ? input[f++] : input[l++];
    }
    while (f <= mid) {
      tmp[a++] = input[f++];
    }
    while (l <= last) {
      tmp[a++] = input[l++];
    }
    a = 0;
    while (first <= last) {
      input[first++] = tmp[a++];
    }
  }
}
public class SinglyLinkedListTest {

  /**
   * Test of sort method, of class SinglyLinkedList.
   */
  @Test
  public void testSort() {
    System.out.println("sort");
    int[] input = {9, 4, 5, 2, 1, 12, 6, 7, 4, 8, 3, 0, 16, 19, 11};
    SinglyLinkedList linkedList = new SinglyLinkedList();
    for (int i = 0; i < input.length; i++) {
      linkedList.addToTail(input[i]);
    }
    assertTrue(Arrays.equals(input, linkedList.toArray()));
    Arrays.sort(input);
    assertFalse(Arrays.equals(input, linkedList.toArray()));
    linkedList.sort();
    assertTrue(Arrays.equals(input, linkedList.toArray()));
  }
}