I decided to implement the MergeSort. LinkedList is preferred for MergeSort over an Array because it does not require a lot of random access, and a LinkedList does not require adjacent or unnecessary memory allocation.

```
public static LinkNode mergeSort(LinkNode head) {
if (head == null || head.next == null) return head;
LinkNode cur = head;
int size = 0;
while (cur != null) {
size++;
cur = cur.next;
}
LinkNode left = head;
LinkNode right = null;
int mid = size >> 1;
cur = left;
while (mid > 1) {
cur = cur.next;
mid--;
}
right = cur.next;
cur.next = null;
return merge(mergeSort(left), mergeSort(right));
}
public static LinkNode merge(LinkNode left, LinkNode right) {
if (left == null) return right;
if (right == null) return left;
LinkNode head = (left.data < right.data) ? left : right;
while (left != null && right != null) {
if (left != null && left.next.data < right.data) {
left = left.next;
}
else {
LinkNode temp = left.next;
left.next = right;
right = temp;
left = left.next;
}
}
return head;
}
```