Time complexity of this mergesort algorithm for linkedlists

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;
    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);
        result = a;
        result.next = merge(a.next,b);
    return result;
public int length(Node a){
    int count = 0;
    Node c = a;
    while( c != null){
        c = c.next;
    return count;

Source: Stack Overflow


Share it with your friends!

    Fatal error: Uncaught Exception: 12: REST API is deprecated for versions v2.1 and higher (12) thrown in /home/content/19/9652219/html/wp-content/plugins/seo-facebook-comments/facebook/base_facebook.php on line 1273