# Stooge sort

O Stooge Sort, ou ordenação "Pateta", é um algoritmo de ordenação que se faz do uso das técnicas de divisão e conquista, ou seja, recursivamente o algoritmo realiza partições virtuais da entrada e transforma o problema maior em pequenos subproblemas até que a ordenação seja mínima. A complexidade deste algoritmo é de O(n$^{log3/log1.5}$) = O(n$^{2.7}$). Comparado a outros algoritmos de ordenação mais conhecidos, como o Insertion Sort e o Bubble Sort, ele chega a ser mais lento. Devido à sua ineficiência, recomenda-se que não seja usado na ordenação de grandes volumes de dados.
O nome do algoritmo faz referência a uma comédia norte-americana chamada The Three Stooges (em português, Os Três Patetas), em que Moe batia repetidamente nos outros dois patetas, assim como o Stooge Sort repetidamente ordena 2/3 do array.

## Ideia geral

Segue, abaixo, a explicação do algoritmo:
* Se o valor da esquerda é maior que o valor da direita, troca-se os dois;
* Se houver 3 ou mais elementos no array, então:
** Realizar a chamada recursiva para os 2/3 iniciais do array.
** Realizar a chamada recursiva para os 2/3 finais do array.
** Realizar a chamada recursiva para os 2/3 iniciais do array.
* Caso contrário:
** Retornar o array.
Observação: Para as chamadas recursivas, é necessário obter um arredondamento para cima (teto) de 2/3 do tamanho do array; caso contrário, o algoritmo pode entrar numa chamada infinita de recursão, para arrays de determinado comprimento.

## Relação de Recorrência

Como mostrado no pseudocódigo acima, a relação de recorrência do algoritmo é dada por: T(n) = 3 * T([(2/3) * n]) + O(1).
Aplicando o Teorema Mestre podemos chegar no custo do algoritmo.
Ex: F(n) = 1 = O(n$^c$), onde c = 0, a = 3, b = 3/2 ∴ log3/2 (3) =~ 2.70
Tendo c < log3/2 (3), chegamos no caso 1 do teorema, logo:
T(n) = O(n$^{log3/2(3)}$) ≈ O(n$^{2.70}$).

## Comparação com outros algoritmos

O tempo de execução do algoritmo é o mesmo tanto no melhor caso quanto no pior, pois seu desempenho independe da ordem dos elementos do array de entrada. Logo, quando comparado com outros algoritmos, é fácil perceber que este é o que possui o pior desempenho, como mostra a tabela abaixo:
| Ordenação | Tempo | Tempo | Tempo |
| | Médio | Melhor | Pior |
| Stooge Sort | O(n$^{2.70}$) | O(n$^{2.70}$) | O(n$^{2.70}$) |
| Bubble Sort | O(n$^2$) | O(n$^2$) | O(n$^2$) |
| Bubble Sort Melhorado | O(n$^2$) | O(n) | O(n$^2$) |
| Insertion Sort | O(n$^2$) | O(n) | O(n$^2$) |
| Selection Sort | O(n$^2$) | O(n$^2$) | O(n$^2$) |
| Heap Sort | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) |
| Merge Sort | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) |
| Quicksort | O(n*log(n)) | O(n*log(n)) | O(n$^2$) |
Fonte
Assim o Stooge sort é um dos piores algoritmos de ordenação, em tempo de execução, tendo como concorrente o Bogosort.

## Características

* O Stooge Sort é um algoritmo que realiza a ordenação no mesmo local que estão armazenados os dados, logo, defini-se o mesmo como In-Place.
* Este algoritmo não é estável em alguns casos. Define-se por estável, se dados dois elementos R e S, os quais possuem mesmo valor, se R aparece antes de S na lista original, R aparecerá antes de S na lista ordenada final. No entanto, dependendo de como é realizado o swap - troca entre elementos do array -, a estabilidade não é preservada, característico deste algoritmo.
* O algoritmo possui baixa eficiência, observado em sua complexidade O(n$^{2.7}$), sendo característico que independente da lista está ordenada ou não, o tempo de execução do mesmo, no melhor e no pior caso, preservará sua complexidade.
* O algoritmo não é tão simples (implementação, leitura e manutenção) quando comparado com o Bubble sort, o Selection sort e o Insertion sort, pois o mesmo realiza várias chamadas recursivas que dificultam sua compreensão. Logo, a implementação do mesmo não é indicada para utilização na prática.
* O Stooge Sort não é confiável, pois há possibilidades de que, em alguns casos, suas chamadas recursivas não tenham fim.
* O algoritmo não faz uso de estruturas auxiliares para realizar a ordenação, fazendo assim com que sua complexidade de espaço adicional não seja maior que O(n).