Classificação por inserção
Classificação por inserção – cada elemento é comparado com os anteriores da lista e o elemento é trocado pelo maior, se houver, caso contrário, o loop de comparação interno para. Como os elementos são classificados do primeiro ao último, cada elemento é comparado a uma lista já classificada, o que *possivelmente* reduz o tempo geral de execução. A complexidade de tempo do algoritmo é O(n^2), ou seja, idêntica à variedade da bolha.
Mesclar classificação
Mesclar classificação – a lista é dividida em grupos de um elemento, então os grupos são “mesclados” em pares com comparação simultânea. Na minha implementação, ao mesclar pares, os elementos à esquerda são comparados com os elementos à direita e, em seguida, movidos para a lista resultante; se os elementos à esquerda desaparecerem, todos os elementos à direita serão adicionados ao resultado; lista (sua comparação adicional é desnecessária, pois todos os elementos dos grupos passam por iterações de classificação)< br />O trabalho deste algoritmo é muito fácil de paralelizar; a etapa de fusão de pares pode ser realizada em threads, aguardando o término das iterações no despachante.
Saída do algoritmo para execução de thread único:
["John", "Alice", "Mike", "#1", "Артем", "20", "60", "60", "DoubleTrouble"]
[["John"], ["Alice"], ["Mike"], ["#1"], ["Артем"], ["20"], ["60"], ["60"], ["DoubleTrouble"]]
[["Alice", "John"], ["#1", "Mike"], ["20", "Артем"], ["60", "60"], ["DoubleTrouble"]]
[["#1", "Alice", "John", "Mike"], ["20", "60", "60", "Артем"], ["DoubleTrouble"]]
[["#1", "20", "60", "60", "Alice", "John", "Mike", "Артем"], ["DoubleTrouble"]]
["#1", "20", "60", "60", "Alice", "DoubleTrouble", "John", "Mike", "Артем"]
Saída do algoritmo para execução multithread:
["John", "Alice", "Mike", "#1", "Артем", "20", "60", "60", "DoubleTrouble"]
[["John"], ["Alice"], ["Mike"], ["#1"], ["Артем"], ["20"], ["60"], ["60"], ["DoubleTrouble"]]
[["20", "Артем"], ["Alice", "John"], ["60", "60"], ["#1", "Mike"], ["DoubleTrouble"]]
[["#1", "60", "60", "Mike"], ["20", "Alice", "John", "Артем"], ["DoubleTrouble"]]
[["DoubleTrouble"], ["#1", "20", "60", "60", "Alice", "John", "Mike", "Артем"]]
["#1", "20", "60", "60", "Alice", "DoubleTrouble", "John", "Mike", "Артем"]
A complexidade de tempo do algoritmo é O(n*log(n)), que é um pouco melhor que O(n^2)
Fontes
https://en.wikipedia.org/wiki/Insertion_sort
https://en.wikipedia.org/wiki/Merge_sort
Código fonte
https://gitlab.com/demensdeum /algoritmos/-/árvore/master/sortAlgoritmos/inserçãoSort
https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/mergeSort
