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.
2