Translating recursion to divide and conquer

Question

I'm trying to return the three smallest items in a list. Below is an O(n) solution I've written:

def three_smallest(L):
    # base case
    if (len(L) == 3):
        return sorted(L)
        
    current = L[0]
    (first_smallest,second_smallest,third_smallest) = three_smallest(L[1:])
    
    if (current < first_smallest):
        return (current, first_smallest, second_smallest)
    elif (current < second_smallest):
        return (first_smallest, current, second_smallest)
    elif (current < third_smallest):
        return (first_smallest, second_smallest, current)
    else:
        return (first_smallest,second_smallest,third_smallest)

Now I'm trying to write a divide and conquer approach but I'm not sure how I should divide the list. Any help would be appreciated.

Note that this solution (to my understanding) is NOT divide and conquer. It is just a basic recursive solution as divide and conquer involves dividing a list of length n by integer b, and calling the algorithm on those parts.

Answer 1

For divide and conquer you generally want to divide a set (roughly) in half rather than whittle it away one by one. Perhaps the following would meet your needs?

def three_smallest(L):
    if (len(L) <= 3):    # base case, technically up to 3 (can be fewer)
        return sorted(L)        
    mid = len(L) // 2    # find the midpoint of L
    # find (up to) the 3 smallest in first half, ditto for the second half, pool
    # them to a list with no more than 6 items, sort, and return the 3 smallest
    return sorted(three_smallest(L[:mid]) + three_smallest(L[mid:]))[:3]

Note that due to the inequality in the base case, this implementation does not have a minimum list size requirement.

At the other end of the scale, your original implementation is limited to lists with fewer than a thousand values or it will blow out the recursion stack. The implementation given above was able to handle a list of a million values with no problem.