Implement a sort method

public void sort$()$

Implement any sort algorithm. Do not use any of Java's built$-$in sorting algorithms.

This is my current code. I was able to get close, but the only things that are messed up with it are the shuffles and 'Adding more elements and shuffling' components:

import java.util.AbstractList;

import java.util.Random;

public class MyLinkedList$>$ extends AbstractList $\{$

private Node head;

private int size $=0$;

private static class Node $\{$

E data;

Node next;

Node$($E data$)\{$

this.data $=$ data;

$\}$

$\}$

@Override

public E get$($int index$)\{$

checkIndex$($index$)$;

Node current $=$ head;

for $($int i $=0$; i $$ index; i$++)\{$

current $=$ current.next;

$\}$

return current.data;

$\}$

@Override

public int size$()\{$

return size;

$\}$

@Override

public boolean add$($E e$)\{$

Node newNode $=$ new Nodee$)$;

if $($head $==$ null$)\{$

head $=$ newNode;

$\}$ else $\{$

Node current $=$ head;

while $($current$.$next $!=$ null$)\{$

current $=$ current.next;

$\}$

current.next $=$ newNode;

$\}$

size$++$;

return true;

$\}$

@Override

public void add$($int index, E element$)\{$

if $($index $<mtext></mtext><mn>0</mn><mtext></mtext><mi>|</mi><mi>|</mi>$ index $>$ size$)\{$

throw new IndexOutOfBoundsException$("$Index: $"+$ index $+",$ Size: $"+$ size$)$;

$\}$

Node newNode $=$ new Nodeelement$)$;

if $($index $==0)\{$

newNode.next $=$ head;

head $=$ newNode;

$\}$ else $\{$

Node prev $=$ getNodeAt$($index $-1)$;

newNode.next $=$ prev.next;

prev.next $=$ newNode;

$\}$

size$++$;

$\}$

@Override

public E remove$($int index$)\{$

checkIndex$($index$)$;

Node current $=$ head;

if $($index $==0)\{$

head $=$ head.next;

$\}$ else $\{$

Node prev $=$ getNodeAt$($index $-1)$;

current $=$ prev.next;

prev.next $=$ current.next;

$\}$

size$--$;

return current.data;

$\}$

@Override

public E set$($int index, E element$)\{$

checkIndex$($index$)$;

Node current $=$ getNodeAt$($index$)$;

E oldValue $=$ current.data;

current.data $=$ element;

return oldValue;

$\}$

@Override

public void clear$()\{$

head $=$ null;

size $=0$;

$\}$

public void sort$()\{$

head $=$ mergeSort$($head$)$;

$\}$

private Node mergeSort$($Node node$)\{$

if $($node $==$ null $||$ node.next $==$ null$)\{$

return node;

$\}$

Node middle $=$ getMiddle$($node$)$;

Node nextOfMiddle $=$ middle.next;

middle.next $=$ null;

Node left $=$ mergeSort$($node$)$;

Node right $=$ mergeSort$($nextOfMiddle$)$;

return merge$($left$,$ right$)$;

$\}$

private Node merge$($Node left, Node right$)\{$

Node sorted $=$ null;

if $($left $==$ null$)$ return right;

if $($right $==$ null$)$ return left;

if $($left$.$data.compareTo$($right$.$data

sorted $=$ left;

sorted.next $=$ merge$($left$.$next, right$)$;

$\}$ else $\{$

sorted $=$ right;

sorted.next $=$ merge$($left$,$ right.next$)$;

$\}$

return sorted;

$\}$

private Node getMiddle$($Node node$)\{$

if $($node $==$ null$)$ return node;

Node slow $=$ node, fast $=$ node.next;

while $($fast $!=$ null && fast.next $!=$ null$)\{$

slow $=$ slow.next;

fast $=$ fast.next.next;

$\}$

return slow;

$\}$

public void shuffle$($int times$)\{$

Random rand $=$ new Random$()$;

for $($int i $=0$; i $$ times; i$++)\{$

int index$1=$ rand.nextInt$($size$)$;

int index$2=$ rand.nextInt$($size$)$;

Node node$1=$ getNodeAt$($index$1)$;

Node node$2=$ getNodeAt$($index$2)$;

E temp $=$ node$1.$data;

node$1.$data $=$ node$2.$data;

node$2.$data $=$ temp;

$\}$

$\}$

private Node getNodeAt$($int index$)\{$

checkIndex$($index$)$;

Node current $=$ head;

for $($int i $=0$; i $$ index; i$++)\{$

current $=$ current.next;

$\}$

return current;

$\}$

private void checkIndex$($int index$)\{$

if $($index $<mtext></mtext><mn>0</mn><mtext></mtext><mi>|</mi><mi>|</mi>$ index $>=$ size$)\{$

throw new IndexOutOfBoundsException$("$Index: $"+$ index $+",$ Size: $"+$ size$)$;

$\}$

$\}$

@Override

public String toString$()\{$

StringBuilder sb $=$ new StringBuilder$("[")$;

if $($head $==$ null$)\{$

sb$.$append$("")$;

$\}$ else $\{$

Node current $=$ head;

while $($current $!=$ null$)\{$

sb$.$append$($current$.$data$)$;

if $($current$.$next $!=$ null$)\{$

sb$.$append$(",")$;

$\}$

current $=$ current.next;

$\}$

$\}$

sb$.$append$("]")$;

return sb$.$toString$()$;

$\}$

$\}$