How to get O(n log(n)) from merge sort?

Question

How to get know if i'm using O(nlog(n)) in my merge sort implementation on linked list. What should I input to O(nlog(n)) to know that what the time of my implementation on merge sort.

public static LinkedListNode<T> MergeSortLL<T>(LinkedListNode<T> Head) where T : IComparable<T>
{

    if (Head?.Next == null)
    {
        return Head;
    }
    var middle = GetMiddle(Head);
    var half = middle.Next;
    middle.Next = null;

    Head = Merge(MergeSortLL(Head), MergeSortLL(half));
    return Head;
}

public static LinkedListNode<T> Merge<T>(LinkedListNode<T> Left, LinkedListNode<T> Right) where T : IComparable<T>
{

    var mHead = new LinkedListNode<T>(default(T));
    LinkedListNode<T> curr = mHead;

    while (Left != null && Right != null)
    {
        if (Left.Value.CompareTo(Right.Value) <= 0)
        {
            curr.Next = Left;
            Left = Left.Next;
        }
        else
        {
            curr.Next = Right;
            Right = Right.Next;
        }
        curr = curr.Next;
    }
    curr.Next = (Left == null) ? Right : Left;

    return mHead.Next;
}

public static LinkedListNode<T> GetMiddle<T>(LinkedListNode<T> Head) where T : IComparable<T>
{
    if (Head == null)
    {
        return Head;
    }

    LinkedListNode<T> slow, fast;
    slow = fast = Head;

    while (fast.Next?.Next != null)
    {
        slow = slow.Next;
        fast = fast.Next.Next;
    }
    return slow;
}

You need to analyse your algorithm. How many times would you loop through your sort code for N=16 compared to N=256? — Alex, Feb 15 '16 at 10:23
For example, I've 100 elements in my list, i need to know, how many times it will loop via O(n*log(n)). — semper fi, Feb 15 '16 at 10:28
O(n*log(n)) is an approximation not a function to calculate the _exact_ number of times your method will loop. See: http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it — Mark, Feb 15 '16 at 10:46
Wiki has an example of a bottom up linked list sort that avoids having to scan a list to find the middle of a list. [wiki linked list sort](http://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists). The wiki example is similar to how Microsoft C++ STL implements std::list::sort. — rcgldr, Feb 15 '16 at 23:13

Ivan Stoev · Accepted Answer · 2016-02-15T10:58:53.717

2

Please note that this algorithm is known to perform O(N*log(N)) comparisons. If you want to confirm that (because it's proven), you can put a counter and increment it on each comparison.

For instance

public static int Comparisons;

public static LinkedListNode<T> Merge<T>(LinkedListNode<T> Left, LinkedListNode<T> Right) where T : IComparable<T>
{
    // ...
    Comparisons++;
    if (Left.Value.CompareTo(Right.Value) <= 0)
    // ...
}

and checking it

LinkedListNode<int> head = ...;
Comparisons = 0;
head = MergeSortLL(head);
Debug.Print(Comparisons);

But note that this algorithm is also known to have a significant hidden cost (finding the middle, even with slow/fast pointer technique).

edited Feb 15 '16 at 10:58

answered Feb 15 '16 at 10:46

Ivan Stoev

195,425
15
312
343

So I need to increment 2 while loops(in merge method and in GetMiddle), ,then, I need to compare the Comparisons value and result of n*log(n). Am I right? – semper fi Feb 15 '16 at 10:55
Oops, I've copied the wrong method. I meant to increment the count in the method where the `Compare` occurs. – Ivan Stoev Feb 15 '16 at 10:59

score 1 · Answer 2 · answered Feb 15 '16 at 10:25

What you can do is add a counter parameter (a reference) to your sort method and increment it every time you enter in a loop. Then you compare this counter to the complexicity of the number of element you trying to sort (let's call that amount N). Then you will see if you are more in O(NlogN) or more in O(N²).

For exemple if your counter is 30 when trying to sort N =10 elements, as 10*log(10) = 23,02... and 10² = 100 you see that you are more in O(NlogN) than in O(N²).

How to get O(n log(n)) from merge sort?

2 Answers2