By user7942761

I’ve run this algorithm and I know that it works but I’m not too sure about its worst case time complexity.

I think that the worst case time complexity for this mergesort algorithm is O(n log n). I would be thankful for anyone that can provide a second opinion.

```
//The main function
public Node mergeSort(Node a){
Node oldHead = a;
int mid = length(a)/2;
if(a == null || a.next == null)
return a;
while(mid-1 > 0){
oldHead = oldHead.next;
mid--;
}
Node newHead = oldHead.next;
oldHead.next = null;
oldHead = a;
Node t1 = mergeSort(oldHead);
Node t2 = mergeSort(newHead);
return merge(t1,t2);
}
public Node merge(Node a, Node b){
Node result = head;
if(a == null)
return b;
if(b == null)
return a;
if(b.name.compareTo(a.name) <= 0){
result = b;
result.next = merge(a,b.next);
}
else{
result = a;
result.next = merge(a.next,b);
}
return result;
}
public int length(Node a){
int count = 0;
Node c = a;
while( c != null){
count++;
c = c.next;
}
return count;
}
```

Source: Stack Overflow