Nas aulas anteriores estudamos Insertion Sort e Shell Sort. Ambos são algoritmos O(n²) no pior caso — para 100.000 elementos, isso significa até 10 bilhões de comparações. Em aplicações reais, isso é simplesmente inaceitável.

Existe uma barreira natural: qualquer algoritmo de ordenação baseado em comparações precisa de pelo menos O(n log n) comparações no pior caso. Nesta aula chegamos a esse limite com dois algoritmos clássicos baseados no paradigma de Divisão e Conquista: Merge Sort e Quick Sort.

Roteiro da aula:

1. Dois conceitos que vamos usar o tempo todo: ordenação estável e ordenação in-place.
2. Divisão e Conquista.
3. Merge Sort.
4. Quick Sort.
5. Comparação geral entre os algoritmos de ordenação.

1. Dois conceitos importantes: estável e in-place

Ao descrever um algoritmo de ordenação, além do tempo de execução, duas propriedades aparecem sempre. Elas serão usadas para comparar o Merge Sort e o Quick Sort, então vale entendê-las bem antes.

1.1 Ordenação estável

Um algoritmo é estável se, quando há elementos com chaves iguais (empates), eles continuam na mesma ordem relativa em que estavam na entrada. Um algoritmo instável pode trocar essa ordem.

Exemplo: uma lista de alunos já em ordem alfabética, que queremos ordenar pela nota. Ana e Caio tiraram 7; Bia e Dani tiraram 9.

• Estável: Ana continua antes de Caio, e Bia antes de Dani (a ordem alfabética dentro de cada nota foi preservada).
• Instável: a lista está correta em relação à nota, mas Caio passou a vir antes de Ana, e Dani antes de Bia. A ordem dos empates foi perdida.

Por que isso importa? A estabilidade permite ordenar por vários critérios em sequência: primeiro ordena-se pelo critério menos importante (nome) e depois, com um algoritmo estável, pelo mais importante (nota). O resultado fica ordenado por nota e, dentro de cada nota, por nome. Se o algoritmo for instável, a segunda ordenação embaralha o que a primeira fez.

Ela só faz diferença quando os elementos têm outras informações além da chave (registros). Para inteiros puros, dois "7" são indistinguíveis e não há como notar a diferença.

1.2 Ordenação in-place

Um algoritmo é in-place ("no lugar") se reorganiza os elementos dentro do próprio vetor, usando apenas uma quantidade constante de memória extra — algumas variáveis como i, j e tmp —, qualquer que seja o tamanho n da entrada. Um algoritmo que precisa de um vetor auxiliar proporcional a n (memória extra O(n)) não é in-place.

Por que isso importa? Ordenar 10 milhões de registros em um algoritmo não in-place exige o dobro da memória: o vetor e uma cópia dele. Em sistemas com memória limitada, isso pode ser inviável.

Observação sobre recursão: um algoritmo recursivo usa a pilha de chamadas. No Quick Sort a pilha ocupa O(log n) em média; por isso ele é chamado de in-place mesmo assim (a memória extra é muito menor que n).

1.3 Onde estão os algoritmos que já conhecemos?

Repare que Merge Sort e Quick Sort são, de certo modo, opostos: um é estável mas gasta memória extra; o outro economiza memória mas não é estável. Vamos ver o porquê ao longo da aula.

2. Divisão e Conquista

Divisão e Conquista é um paradigma de resolução de problemas: um insight fundamental sobre como projetar bons algoritmos e, ao mesmo tempo, uma família de algoritmos para diversos problemas. A ideia: em vez de atacar o problema inteiro de uma vez, quebramos em partes menores, resolvemos cada uma e juntamos as respostas.

1. Dividir a entrada em entradas menores — idealmente em partes iguais, e recursivamente até chegar a algo trivial.
2. Conquistar as entradas triviais — solução direta para n = 1 (ou n = 2).
3. Recombinar as soluções das partes, desfazendo a recursão. Este é o passo mais importante.

Quando se aplica? (E por que não usamos para tudo?) Quando é fácil dividir o problema em instâncias menores e é eficiente combinar as soluções das instâncias menores de volta na solução do problema original. Se não houver como combinar eficientemente, a divisão não ajuda.

Para ordenação, o problema é: "ordenar um vetor de n elementos". O caso base é um vetor de 0 ou 1 elemento — que já está ordenado por definição. Os dois algoritmos desta aula diferem em onde fazem o trabalho pesado:

3. Merge Sort

3.1 Características

O Merge Sort é um algoritmo de ordenação que:

• é independente do tipo de dado: só precisa comparar dois elementos (o mesmo código serve para inteiros, strings, registros);
• é estável (veja 1.1);
• foi criado por John von Neumann em 1945;
• não é in-place: exige um vetor auxiliar do tamanho do vetor, ou seja, o dobro da memória (veja 1.2);
• tem complexidade O(n log n) em todos os casos;
• é "embaraçosamente paralelizável": as duas metades são independentes, então podem ser ordenadas por processadores diferentes, sem nenhuma comunicação entre eles.

3.2 Por que o Merge Sort é Divisão e Conquista?

• Divisão: do vetor ao meio.
• Conquista: vetor com n = 0, 1 (ou 2) elementos.
• Recombinação: de dois subvetores ordenados em um vetor ordenado (o merge).

Temos tudo que é necessário para um bom algoritmo de Divisão e Conquista: dividir é trivial e recombinar é eficiente.

3.3 A recombinação: o Merge

Dados dois subvetores já ordenados e adjacentes, como produzir um único subvetor ordenado de forma eficiente? Como os dois lados estão ordenados, o menor elemento do resultado só pode ser o menor de um dos lados. Basta comparar os dois menores (as "cabeças"), copiar o menor para a saída e avançar no lado de onde ele veio.

Merge(A, start, mid, end)
 1  for i ← start to end
 2      Aux[i] ← A[i]
 3  i = start
 4  j = mid + 1
 5  k = start
 6  while i ≤ mid and j ≤ end
 7      if Aux[i] ≤ Aux[j]
 8          A[k] ← Aux[i]
 9          i ← i + 1
10      else A[k] ← Aux[j]
11          j ← j + 1
12      k ← k + 1
13  while i ≤ mid
14      A[k] ← Aux[i]
15      i ← i + 1
16      k ← k + 1
17  while j ≤ end
18      A[k] ← Aux[j]
19      j ← j + 1
20      k ← k + 1

• Há um vetor auxiliar Aux que recebe a porção do vetor a ser ordenada (linhas 1-2), contendo os dois subvetores já ordenados.
• i aponta para o início do primeiro subvetor em Aux; j aponta para o início do segundo; k aponta para a posição de A onde os elementos serão inseridos.
• O laço das linhas 6-12 compara o menor de cada subvetor e coloca o menor na saída.
• Os laços das linhas 13-16 e 17-20 copiam o que sobrou de um dos subvetores quando o outro já acabou.

Exemplo passo a passo. Merge de [1, 4, 7, 9] com [2, 5, 6, 8]. Na linha de cima estão os valores de Aux (azul = Aux[i], amarelo = Aux[j], cinza = já copiado); na de baixo, o vetor A sendo preenchido (verde):

Cada passo faz uma única comparação e copia um elemento. O merge de subvetores com k elementos no total custa O(k).

3.4 A divisão: MergeSort

MergeSort(A, start, end)
1  if start < end
2      mid ← ⌊(start + end) / 2⌋
3      MergeSort(A, start, mid)
4      MergeSort(A, mid + 1, end)
5      Merge(A, start, mid, end)

• start e end representam os índices de início e fim da parte do vetor a ser ordenada.
• Para ordenar o vetor inteiro, é preciso chamar MergeSort(A, 1, length(A)).
• A divisão é trivial: só calcular o índice do meio. Todo o trabalho inteligente está no Merge.

3.5 Exemplo completo: o diagrama da recursão

Vamos ordenar [38, 27, 43, 3, 9, 82, 10]. No desenho, as setas vermelhas descem (dividir), os quadrados cinzas são a conquista (vetores de 1 elemento, já ordenados) e as setas verdes sobem (recombinar, com o Merge).

A ordem real de execução é em profundidade: a metade esquerda é inteiramente ordenada antes de a direita começar. Os merges acontecem nesta ordem:

1. Merge([38], [27]) → [27, 38]
2. Merge([43], [3]) → [3, 43]
3. Merge([27, 38], [3, 43]) → [3, 27, 38, 43]  (a metade esquerda está pronta)
4. Merge([9], [82]) → [9, 82]
5. Merge([9, 82], [10]) → [9, 10, 82]  (a metade direita está pronta)
6. Merge([3, 27, 38, 43], [9, 10, 82]) → [3, 9, 10, 27, 38, 43, 82]

3.6 A conquista e a dinâmica em sala

A conquista é realmente trivial: se um vetor é vazio ou unitário, ele já está ordenado. Também dá para conquistar já em n = 2 (compara os dois elementos e, se preciso, troca).

Com a pilha [6, 5, 3, 1, 8, 7, 2, 4] e conquista em n = 2, a dinâmica fica assim (cada caixa é um aluno):

3.7 Análise de complexidade

Como calcular o esforço total? Somando o esforço de todos os nós (alunos/chamadas) da árvore de recursão. O jeito mais fácil: em um mesmo nível, todos os nós fazem o mesmo esforço, então calculamos o esforço somado de cada nível:

• Profundidade 0: um merge de n elementos → n.
• Profundidade 1: dois merges de n/2 elementos → n/2 + n/2 = n.
• Profundidade 2: quatro merges de n/4 elementos → n.
• … e assim por diante, até o último nível: n.

Se o custo é o mesmo em cada nível, basta multiplicar pelo número de níveis. Quantos níveis (k) há? Dividimos n ao meio até chegar ao caso base (tamanho 2, na dinâmica acima):

n / 2^k = 2   ⇒   n = 2^(k+1)   ⇒   log2(n) = k + 1   ⇒   k = log2(n) - 1

Custo do nível × número de níveis = O(n) × O(log n) = O(n log n).

A função de recorrência. Basicamente todo algoritmo de Divisão e Conquista tem uma recorrência, que descreve o custo T(n) em função do custo dos subproblemas. A do Merge Sort é:

T(n) = 2 T(n/2) + n

Por quê? São duas chamadas recursivas (o 2), cada uma sobre metade do vetor (o n/2), mais o custo da recombinação, o Merge, que é linear (o + n).

3.8 Código em C

O código abaixo segue o pseudocódigo das seções anteriores (com índices a partir de 0). O maior empecilho prático é mesclar sem sobrescrever: a única forma de não estragar a complexidade é ter um vetor extra (aux) para guardar a cópia sobre a qual a mescla é feita. Existe uma variação mais esperta (alternating buffers: alternar os papéis de A e Aux a cada nível, evitando a cópia a cada merge), mas ela deixa o código mais enigmático; aqui usamos a versão simples.

#include 

/* Intercala a[ini..meio] e a[meio+1..fim], ambos já ordenados. */
void merge(int a[], int aux[], int ini, int meio, int fim) {
    int t, i, j, k;

    for (t = ini; t <= fim; t++)      /* linhas 1-2: copia para Aux */
        aux[t] = a[t];

    i = ini;  j = meio + 1;  k = ini; /* linhas 3-5 */

    while (i <= meio && j <= fim) {   /* linhas 6-12 */
        if (aux[i] <= aux[j])         /* <= (e não <) mantém a estabilidade */
            a[k++] = aux[i++];
        else
            a[k++] = aux[j++];
    }
    while (i <= meio) a[k++] = aux[i++];  /* linhas 13-16 */
    while (j <= fim)  a[k++] = aux[j++];  /* linhas 17-20 */
}

void mergeSortRec(int a[], int aux[], int ini, int fim) {
    if (ini >= fim) return;               /* conquista: 0 ou 1 elemento */
    int meio = ini + (fim - ini) / 2;     /* divisão: ao meio */
    mergeSortRec(a, aux, ini, meio);
    mergeSortRec(a, aux, meio + 1, fim);
    merge(a, aux, ini, meio, fim);        /* recombinação */
}

void mergeSort(int a[], int n) {
    int *aux = malloc(n * sizeof(int));   /* o vetor extra: O(n) de memória */
    mergeSortRec(a, aux, 0, n - 1);
    free(aux);
}

3.9 Complexidade e quando usar

Vale a pena? O(n log n) é (muito) menor que O(n²). Para n = 10⁶: n² = 10¹² operações, enquanto n log₂ n ≈ 2 × 10⁷ — cerca de 50 mil vezes menos.

Piada de matemático vs. engenheiro: quanto é o limite de log(n) quando n tende ao infinito? O matemático diz "infinito". O engenheiro lembra que o número de partículas do universo observável é cerca de 10⁸⁰ ≈ 2²⁷²: para qualquer n fisicamente possível, log₂ n ≤ 272. Na prática, log n é quase uma constante.

Quando usar Merge Sort:

• Quando a estabilidade é obrigatória (ex.: ordenar uma tabela por dois campos em sequência).
• Para listas ligadas (o merge em listas não requer espaço extra e é naturalmente eficiente).
• Para dados em disco (merge sort externo): disco magnético favorece acesso sequencial, que é exatamente o padrão do merge.
• Quando se precisa de garantia incondicional de O(n log n).

4. Quick Sort

4.1 Características

O Quick Sort é um algoritmo de ordenação que:

• é independente do tipo de dado;
• é instável (veja 1.1);
• foi criado por Tony Hoare em 1959 (depois do Merge Sort);
• é in-place: não exige vetor auxiliar, só uma quantidade (quase) constante de memória extra — a pilha de recursão, O(log n) em média (veja 1.2);
• tem pior caso O(n²) ("ruim"), mas ele é raro; com alguns truques estatísticos o desempenho esperado é O(n log n);
• é paralelizável (com seus problemas).

Vale a pena? Sim, em muitos casos: a instabilidade é irrelevante quando não há empates que importem; com os truques certos o tempo é O(n log n); e não alocar memória extra às vezes é muito importante.

4.2 Por que o Quick Sort é Divisão e Conquista?

• Divisão: do vetor em "metades", em torno de um elemento chamado pivô: os menores ficam de um lado, os maiores do outro, e o pivô fica na posição certa.
• Conquista: vetor com n = 0, 1 (ou 2) elementos.
• Recombinação: não é necessária! Os dois lados já estão separados e o pivô já está no lugar.

O maior problema é que a divisão não é bem na metade: ela depende do pivô. Mais adiante veremos o que isso causa.

4.3 A divisão: Quicksort e Partition

Quicksort(A, start, end)
1  if start < end
2      p = Partition(A, start, end)
3      Quicksort(A, start, p - 1)
4      Quicksort(A, p + 1, end)

Partition(A, a, b)
1  x = A[b]                  ← o pivô é o último elemento
2  i = a - 1
3  for j ← a to b - 1
4      if A[j] ≤ x
5          i = i + 1
6          swap(A[i], A[j])
7  swap(A[i + 1], A[b])
8  return i + 1

Depois de Partition, já separamos os menores para um lado e os maiores para o outro, com um elemento no meio (o pivô) na posição certa. A peça-chave é o Partition, que usa o último elemento como pivô x e mantém, durante o laço, três regiões:

• A[a..i]: elementos ≤ x (verde);
• A[i+1..j-1]: elementos > x (laranja);
• A[j..b-1]: elementos ainda não examinados (branco). O pivô (azul) fica em A[b].

4.4 Partition passo a passo

Vamos particionar [5, 1, 4, 2, 8, 3], com pivô x = 3 (o último). Os números acima das caixas são os índices; a caixa com borda grossa laranja é A[j]:

O pivô 3 está agora em sua posição final definitiva. As duas recursões seguintes ordenarão [1, 2] e [5, 8, 4] independentemente. Repare também que a troca A[i] ↔ A[j] move elementos para longe de onde estavam: é isso que torna o Quick Sort instável (veja o exercício 4).

4.5 Exemplo completo: a árvore de recursão

Cada caixa mostra o subvetor depois de particionado: azul = pivô (já na posição final), verde = menores ou iguais, laranja = maiores. Os cinzas são subvetores de 1 elemento (conquista).

Resultado: [1, 2, 3, 4, 5, 8]. Note que não há nenhuma fase de "recombinar": ao final das recursões, o vetor já está ordenado.

4.6 Complexidade: o pior caso e a escolha do pivô

O Quick Sort é O(n log n) no caso médio, mas pode degenerar para O(n²). E se o vetor está ordenado (ao contrário)?

• Com o pivô sendo o último elemento (o menor de todos, em um vetor decrescente), o índice i nunca avança: todos os elementos são maiores que o pivô.
• A divisão resulta em subvetores de tamanho 0 e n − 1.
• Repetindo, o trabalho total é (n − 1) + (n − 2) + (n − 3) + … + 1 = O(n²).

O mesmo acontece com um vetor já ordenado em ordem crescente: o pivô (último elemento) é o maior de todos e a partição também separa n − 1 elementos de um lado e 0 do outro. A raiz do problema: a divisão não é bem na metade.

Há como fazer uma escolha inteligente do pivô? Sim:

Solução 1 — Pivô aleatório: escolher um índice aleatório, trocá-lo com o último e então aplicar a partição. Isso dá O(n log n) em valor esperado, para qualquer entrada.

#include    /* rand() */

void quickSortAleatorio(int a[], int esq, int dir) {
    if (esq >= dir) return;

    /* escolhe um índice aleatório e o troca com o último */
    int r = esq + rand() % (dir - esq + 1);
    int tmp = a[r]; a[r] = a[dir]; a[dir] = tmp;

    int p = particionar(a, esq, dir);
    quickSortAleatorio(a, esq, p - 1);
    quickSortAleatorio(a, p + 1, dir);
}

Solução 2 — Mediana de três: usar como pivô a mediana entre a[esq], a[(esq+dir)/2] e a[dir]. Evita o pior caso para vetores ordenados ou quase ordenados, que são entradas comuns na prática. (Existe até um algoritmo que acha a mediana exata em O(n), mas na prática ele é caro demais para compensar.)

4.7 Código em C

int particionar(int a[], int esq, int dir) {
    int pivo = a[dir];   /* x = A[b]: o último elemento é o pivô */
    int i = esq - 1;
    int j, tmp;

    for (j = esq; j < dir; j++) {
        if (a[j] <= pivo) {
            i++;
            tmp = a[i]; a[i] = a[j]; a[j] = tmp;   /* swap(A[i], A[j]) */
        }
    }
    tmp = a[i + 1]; a[i + 1] = a[dir]; a[dir] = tmp; /* pivô para a posição final */
    return i + 1;
}

void quickSort(int a[], int esq, int dir) {
    if (esq >= dir) return;              /* conquista: 0 ou 1 elemento */
    int p = particionar(a, esq, dir);    /* divisão: faz o trabalho */
    quickSort(a, esq, p - 1);
    quickSort(a, p + 1, dir);            /* recombinação: nada a fazer */
}

4.8 Complexidade e quando usar

Quando usar Quick Sort:

• Dados em memória principal, onde a localidade de cache importa — o Quick Sort acessa a memória de forma mais sequencial que o Merge Sort e é geralmente mais rápido na prática.
• Quando o espaço extra O(n) do Merge Sort é inaceitável.
• Caso geral sem requisito de estabilidade.

5. Comparação Geral dos Algoritmos de Ordenação

* Espaço da pilha de recursão no caso médio com pivô aleatório; O(n) no pior caso.

Resumo

Exercícios

1. Trace o Merge Sort completo no array [9, 3, 7, 1, 5, 8, 2, 6]. Mostre a árvore de recursão completa (fase dividir) e todos os passos da fase combinar (merges intermediários e seus resultados).


2. Por que o Merge Sort é O(n log n) em todos os casos, enquanto o Quick Sort pode ser O(n²) no pior caso? Qual é a diferença estrutural entre os dois que explica esse comportamento?


3. Trace a partição (esquema de Lomuto) no array [4, 7, 2, 9, 1, 5, 3] com pivô = 3 (último elemento). Qual é o estado do array após a partição? Em que índice o pivô fica?


4. Por que o Quick Sort não é estável? Dê um exemplo concreto com elementos iguais mostrando como a ordem relativa deles pode ser alterada durante a partição.


5. Você precisa ordenar 10 milhões de registros de um banco de dados pelo sobrenome e depois pelo primeiro nome. Qual algoritmo é mais apropriado: Quick Sort ou Merge Sort? Por quê?


6. Um array está ordenado em ordem crescente. Qual é o desempenho de: (a) Merge Sort? (b) Quick Sort com último elemento como pivô? (c) Insertion Sort?


7. O Quick Sort com pivô aleatório tem complexidade O(n log n) esperada. O que significa "esperada" aqui? Ainda é possível obter O(n²)?


8. O Merge Sort requer O(n) de espaço extra para os vetores temporários. Como seria possível implementar Merge Sort em listas ligadas sem espaço extra? (Resposta conceitual, sem código.)


9. O std::sort do C++ (Introsort) começa com Quick Sort mas troca para Heap Sort quando a profundidade da recursão ultrapassa 2 log n. Por que esse limite e por que Heap Sort especificamente?


10. Classifique cada algoritmo como estável ou instável e como in-place ou não in-place: Insertion Sort, Selection Sort, Merge Sort e Quick Sort. Justifique cada resposta em uma frase.


11. Execute a partição (esquema do Partition dos slides) no vetor [5, 4, 3, 2, 1]. O que acontece com o índice i? Em que posição fica o pivô e em que tamanhos o vetor é dividido? O que isso diz sobre o pior caso?


12. Execute o Merge Sort com conquista em n = 2 (a dinâmica da aula) no vetor [7, 2, 9, 4, 1, 8, 3, 6]. Mostre a divisão, a conquista e todos os merges, e diga quantos merges são feitos no total.

Gabaritos

FASE DIVIDIR:
Nível 0: [9, 3, 7, 1, 5, 8, 2, 6]
          ────────────┬────────────
Nível 1: [9, 3, 7, 1]   [5, 8, 2, 6]
          ─────┬─────   ─────┬─────
Nível 2: [9,3] [7,1]   [5,8] [2,6]
          ─┬─  ─┬─     ─┬─   ─┬─
Nível 3: [9][3] [7][1] [5][8] [2][6]   ← casos base

FASE COMBINAR (de baixo para cima):
Nível 3→2:
  merge([9],[3])  → compara 9 vs 3: copia 3, depois 9 → [3, 9]
  merge([7],[1])  → compara 7 vs 1: copia 1, depois 7 → [1, 7]
  merge([5],[8])  → compara 5 vs 8: copia 5, depois 8 → [5, 8]
  merge([2],[6])  → compara 2 vs 6: copia 2, depois 6 → [2, 6]

Nível 2→1:
  merge([3,9],[1,7]):
    3 vs 1 → copia 1
    3 vs 7 → copia 3
    9 vs 7 → copia 7
    restante: copia 9
    resultado: [1, 3, 7, 9]

  merge([5,8],[2,6]):
    5 vs 2 → copia 2
    5 vs 6 → copia 5
    8 vs 6 → copia 6
    restante: copia 8
    resultado: [2, 5, 6, 8]

Nível 1→0:
  merge([1,3,7,9],[2,5,6,8]):
    1 vs 2 → copia 1
    3 vs 2 → copia 2
    3 vs 5 → copia 3
    7 vs 5 → copia 5
    7 vs 6 → copia 6
    7 vs 8 → copia 7
    9 vs 8 → copia 8
    restante: copia 9
    resultado: [1, 2, 3, 5, 6, 7, 8, 9]  ✓

Array: [4, 7, 2, 9, 1, 5, 3]   pivô = 3
        0  1  2  3  4  5  6

i = -1

j=0: a[0]=4.  4 > 3? Sim, ignora. i=-1.
j=1: a[1]=7.  7 > 3? Sim, ignora. i=-1.
j=2: a[2]=2.  2 ≤ 3? Sim. i++ → i=0. Troca a[0] ↔ a[2].
     [2, 7, 4, 9, 1, 5, 3]
j=3: a[3]=9.  9 > 3? Sim, ignora. i=0.
j=4: a[4]=1.  1 ≤ 3? Sim. i++ → i=1. Troca a[1] ↔ a[4].
     [2, 1, 4, 9, 7, 5, 3]
j=5: a[5]=5.  5 > 3? Sim, ignora. i=1.

Fim do laço. Troca a[i+1]=a[2] com pivô a[6]:
     [2, 1, 3, 9, 7, 5, 4]
            ^
            pivô 3 em índice 2.

Estado final: [2, 1, 3, 9, 7, 5, 4]
Índice do pivô: 2.
Lado esquerdo (0..1): [2, 1] — ambos ≤ 3  ✓
Lado direito  (3..6): [9, 7, 5, 4] — todos > 3  ✓

Array: [(3,A), (1,B), (3,C), (2,D)]
Queremos ordenar pelo valor. Os dois "3" (A e C) deveriam manter a
ordem A antes de C em um algoritmo estável.

Pivô = (2,D) (último elemento).

i=-1
j=0: (3,A) > 2? Sim, ignora.
j=1: (1,B) ≤ 2? Sim. i=0. Troca a[0] ↔ a[1]:
     [(1,B), (3,A), (3,C), (2,D)]
j=2: (3,C) > 2? Sim, ignora.

Fim. Troca a[1] ↔ a[3] (pivô):
     [(1,B), (2,D), (3,C), (3,A)]
                    ^^^^   ^^^^
                    C antes de A — ordem invertida!

O elemento (3,C), que originalmente vinha DEPOIS de (3,A), agora está
ANTES dele. A ordem relativa foi destruída. Algoritmo não estável.

Vetor: [5, 4, 3, 2, 1]   pivô x = A[b] = 1     i = -1

j=0: A[0]=5 > 1  → ignora        i continua -1
j=1: A[1]=4 > 1  → ignora        i continua -1
j=2: A[2]=3 > 1  → ignora        i continua -1
j=3: A[3]=2 > 1  → ignora        i continua -1

Fim do laço: swap(A[i+1], A[b]) = swap(A[0], A[4])
     [1, 4, 3, 2, 5]
      ^
      pivô 1 no índice 0

DIVISÃO:
[7, 2, 9, 4, 1, 8, 3, 6]
[7, 2, 9, 4]               [1, 8, 3, 6]
[7, 2]   [9, 4]            [1, 8]   [3, 6]       ← tamanho 2: conquista

CONQUISTA (compara e troca, se preciso):
[7, 2] → [2, 7]    [9, 4] → [4, 9]    [1, 8] → [1, 8]    [3, 6] → [3, 6]

RECOMBINAÇÃO (merges):
Merge([2, 7], [4, 9])     → [2, 4, 7, 9]
Merge([1, 8], [3, 6])     → [1, 3, 6, 8]
Merge([2, 4, 7, 9], [1, 3, 6, 8]) → [1, 2, 3, 4, 6, 7, 8, 9]