java - 这种链表合并排序算法的时间复杂度

Question

我已经运行了这个算法，我知道它可以工作，但我不太确定它的最坏情况下的时间复杂度。我认为这个合并排序算法的最坏情况时间复杂度是 O(n log n)。如果有人能提供第二意见，我将不胜感激。

//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;
}

Answer 1

是的，这仍然是 O(n log(n))。与传统的合并排序算法相比，这里没有任何改变来改变它的时间复杂度。与链表的唯一真正区别是将列表一分为二。这具有 O(n) 的复杂性，但它与同样具有复杂性 O(n) 的合并操作处于同一级别。所以它对复杂性没有整体影响。

编辑。长度操作是 O(n)，但它与拆分操作和合并操作处于同一级别，它们也是 O(n)，因此它也不会影响时间复杂度。