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.