Considere os algoritmos clássicos de ordenação: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort e Quick Sort.

Analise as afirmativas a seguir com base em suas propriedades formais de complexidade, estabilidade e uso de memória na implementação tradicional apresentada na literatura clássica.

I. O Insertion Sort possui complexidade de tempo O(n²) no pior caso e pode apresentar complexidade O(n) no melhor caso, quando o vetor já se encontra ordenado.

II. O Merge Sort apresenta complexidade O(n log n) nos casos melhor, médio e pior, é estável e, em sua implementação tradicional, requer espaço adicional proporcional a O(n).

III. O Quick Sort apresenta complexidade média O(n log n) e pior caso O(n²), podendo este ocorrer quando o pivô escolhido produz partições altamente desbalanceadas.

IV. O Selection Sort possui complexidade O(n²) nos casos melhor, médio e pior e, em sua implementação tradicional, não é considerado um algoritmo estável.

Assinale a alternativa CORRETA: