O paradigma divide e conquista em ciência da computação é uma técnica para dividir recursivamente problemas em subproblemas menores. Um dos aspectos principais dessa técnica é a recursão, que acontece quando uma função chama a si mesma repetidamente até que um caso base seja alcançado. Nesta lição, vamos analisar o algoritmo merge sort para entender melhor como a técnica divide e conquista funciona. Vamos supor que temos esta lista de números:

42 37 53 17

O objetivo é ordenar essa lista do menor para o maior usando o algoritmo merge sort. O primeiro passo é dividir essa lista ao meio:

42 37 | 53 17

Então precisamos olhar para o lado esquerdo da lista:

42 37

Pegamos essa sublista e dividimos ao meio novamente até que cada sublista tenha apenas um item:

42 | 37

Uma lista com apenas um item é ordenada por padrão. Em seguida, precisamos mesclar cada uma dessas sublistas de um elemento em uma lista ordenada:

37 42

Então seguimos o mesmo processo para o lado direito da lista original:

# right side of original list
53 17

# divide the list in half
53 | 17

# merge the lists in sorted order
17 53

Agora que ambas as metades da lista original estão ordenadas, nós unimos essas duas metades e ordenamos os elementos:

17 37 42 53

Aqui está como o algoritmo se parece em código:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    sorted_list = []
    i = 0
    j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            sorted_list.append(left[i])
            i += 1
        else:
            sorted_list.append(right[j])
            j += 1

    sorted_list.extend(left[i:])
    sorted_list.extend(right[j:])

    return sorted_list

A complexidade de tempo para merge sort seria O(n log n) porque a lista é continuamente dividida ao meio (log n) e depois mesclada (O(n)). Ao contrário de outros algoritmos de ordenação como bubble sort, merge sort não é ordenado in place e tem uma complexidade de espaço de O(n).