Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.