I'd like to start by stating this isn't homework! I'm studying for a job interview and would appreciate a second opinion. (Well, I guess it is homework, but not for school!).
I've written an algorithm (see pseudocode below) to merge two sorted lists into one sorted list. The problem requires that I implement it as a recursive divide-and-conquer algorithm. My algorithm is recursive and works but does it count as divide-and-conquer?
The reason I'm asking is that the other people working on the same problem insist D&C must divide the lists in half every time and have $O(n \log n)$ complexity, like quicksort and mergesort. My algorithm doesn't divide the lists in the middle and has a complexity of $O(n+m)$ (where $n$ and $m$ are the lengths of the lists).
To summarize my question: Does a D&C algorithm have to have $O(n \log n)$ complexity and divide the problem in half every time? Or does this algorithm count as D&C?
merge_sorted_lists(list1, list2) if(list1 and list2 are empty) return empty list if(list1 is empty) return list2 else if(list2 is empty) return list1 else if(head of list1 < head of list2) smaller = pop head of list1 else if(head of list2 < head of list1) smaller = pop head of list2 return smaller + merge_sorted_lists(list1, list2)
P.S. I've implemented the algorithm in Java and it works.