Estrutura básica

int solve(vector<int> a) {
   int n = a.size();
   if (n == 1) return solucao(a);
   
   // divide
   vector<int> vl = a[0..n/2];
   vector<int> vr = a[n/2..n];

   // pega a resposta pra cada metade
   solucao_left = solve(vl);
   solucao_right = solve(vr);

   // "conquista"
   return merge(solucao_left, solucao_right);   
}

Alguns exemplos "clássicos" (geeksforgeeks)

  1. Quicksort: ordenação de array escolhendo um pivot
  2. Merge Sort: ordenação de array dividindo na metade
  3. **Closest Pair of Points:** problema de Geometry, encontrar o par de pontos mais próximos entre si em O(nlogn)
  4. Strassen’s Algorithm: multiplicação de duas matrizes em O(n^2.8974) em vez de O(n^3)
  5. Cooley–Tukey Fast Fourier Transform (FFT) algorithm: método mais conhecido para calcular o FFT em O(nlogn)
  6. Karatsuba algorithm for fast multiplication: multiplicação de BigIntegers (numeros com muitos dígitos)
  7. Inversion count: contagem de inversões de um array (uma inversão é $a[i]>a[j], i<j$) em O(nlogn), com a mesma ideia do MergeSort.

Exercícios auxiliares

A - Permutation Transform

B - a-Good String