# Help with algorithmic complexity in custom merge sort implementation

I've got an implementation of the merge sort in C++ using a custom doubly linked list. I'm coming up with a big O complexity of n^2, based on the `merge_sort()` > `slice` operation. But, from what I've read, this algorithm should be `n*log(n)`, where the log has a base of two.

Can someone help me determine if I'm just determining the complexity incorrectly, or if the implementation can/should be improved to achieve `n*log(n)` complexity?

If you would like some background on my goals for this project, see my blog. I've added comments in the code outlining what I understand the complexity of each method to be.

Clarification - I'm focusing on the C++ implementation with this question. I've got another implementation written in Python, but that was something that was added in addition to my original goal(s).

-

You're determining the complexity incorrectly. The standard mergesort recurrence is

``````T(n) = 2 T(n/2) + O(n)
``````

Since your `slice` is indeed `O(n)`, you're fine.

As a minor optimisation, though, you might want to consider having a single method to split the list in two which doesn't involve iterating down the first half of the list twice.

-
Thanks for the answer here. I'm trying to understand your suggested optimization. I assume you're talking about the `slice` method, but I don't see where its iterating down the first half twice. – bitcycle Nov 26 '12 at 1:27
@bitcycle, `left = original->slice(0,(len/2)); right = original->slice((len/2)+1,len-1);` between them appear to iterate over the list 1.5 times. – Peter Taylor Nov 26 '12 at 7:25