Evoluindo um Merge Sort: de primitivos a collections

Comecei recentemente a estudar algoritmos e estruturas de dados e estou realizando as implementações desses algoritmos em Java.

Em Java, temos muitas opções de como realizar essas implementações, justamente pelo legado deixado em cada versão em sua biblioteca padrão. O primeiro algoritmo que vi foi Merge Sort.

O que é Merge Sort?

Merge Sort é um algoritmo de ordenação que adota a estratégia Divide-and-Conquer. Ou seja, ela pega um problema maior e divide em vários sub-problemas, resolvendo primeiramente estes sub-problemas para proceder com uma computação a mais para resolver o problema maior a paritr da resolução desses sub-problemas.

Dito isso, podemos pegar um Array de números por exemplo para poder fazer ordenar ele e dividir este array em vários pequenos arrays, até uma parte atômica. Ordenamos essa parte atômica e vamos juntando estas soluções até formar um array que esteja completamente ordenado. Isto é o Merge Sort.

Implementando

Para saber que minha implementação está correta, vou utilizar um approach básico de TDD: primeiro vou escrever um teste para depois escrever a implementação em si.

O teste é simples:

public class MergeSortTest {

  @Test
  public void shouldGiveASortedArray () {
    final var inputArray = new int[]{ 5, 4, 1, 8, 7, 2, 6, 3 };
    final var desiredArray = new int[]{ 1, 2, 3, 4, 5, 6, 7, 8 };

    var sorted = MergeSort.sort(inputArray);

    IntStream.range(0, sorted.length).forEach(i -> {
      assertEquals(desiredArray[i], sorted[i]);
    });
  }
}

Aqui, estou levando em consideração que em Java, arrays primitivos são reference types. O assertEquals faz uma comparação simples (utilizando um ==) entre cada um dos comparados. Sendo assim, é melhor destrinchar cada um dos itens e fazer essa comparação para assegurar que a ordem está correta!

Primeira implementação: usando apenas primitivos e operações primitivas

A primeira implementação é aquela crua e que é feita para fazer funcionar de fato:

public class MergeSort {
  public static int[] sort (int[] unsorted) {
    var length = unsorted.length;

    if (length == 1) return unsorted;

    if (length == 2) {
      if (unsorted[0] > unsorted[1]) {
        var placeholder = unsorted[1];
        unsorted[1] = unsorted[0];
        unsorted[0] = placeholder;
      }

      return unsorted;
    }

    int halfArrLength = length / 2;

    int[] firstHalf = Arrays.copyOfRange(unsorted, 0, halfArrLength);
    int[] secondHalf = Arrays.copyOfRange(unsorted, halfArrLength, length);

    var firstHalfSorted = sort(firstHalf);
    var secondHalfSorted = sort(secondHalf);
    var outputSorted = new int[length];
    var firstIndex = 0;
    var secondIndex = 0;

    for (int i = 0; i < length; i++) {
      if (firstIndex >= firstHalfSorted.length) {
        outputSorted[i] = secondHalfSorted[secondIndex];
        secondIndex++;
        continue;
      }

      var oneTerm = firstHalfSorted[firstIndex];

      if (secondIndex >= secondHalfSorted.length) {
        outputSorted[i] = firstHalfSorted[firstIndex];
        firstIndex++;
        continue;
      }

      var secondTerm = secondHalfSorted[secondIndex];

      if (oneTerm < secondTerm) {
        outputSorted[i] = oneTerm;
        firstIndex++;
      } else {
        outputSorted[i] = secondTerm;
        secondIndex++;
      }
    }

    return outputSorted;
  }
}

Podemos ver que nesse caso, estamos fazendo de fato uma manipulação muito crua dos arrays e não estamos tirando nenhuma vantagem do que a biblioteca padrão de Java nos oferece. Tecnicamente poderíamos realizar tudo isso com operadores de baixo nível e zero abstração, sem utilizar qualquer classe externa.

Segunda implementação: limpando o código e utilizando alguns recursos

public class MergeSort {
  public static int[] sort (int[] unsorted) {
    var length = unsorted.length;

    if (length == 1) return unsorted;

    if (length == 2) {
      var firstOfUnsorted = unsorted[0];
      var secondOfUnsorted = unsorted[1];

      if (firstOfUnsorted > secondOfUnsorted) {
        unsorted[1] = firstOfUnsorted;
        unsorted[0] = secondOfUnsorted;
      }

      return unsorted;
    }

    int halfArrLength = length / 2;

    var firstHalfSorted = copyAndSort(unsorted, 0, halfArrLength);
    var secondHalfSorted = copyAndSort(unsorted, halfArrLength, length);

    var outputSorted = new int[length];
    var firstIndex = 0;
    var secondIndex = 0;

    for (int i = 0; i < length; i++) {
      final var actualIndex = i;

      Consumer<Integer> assignToOutput =
          (value) -> outputSorted[actualIndex] = value;

      if (isGreatherOrEquals(firstIndex, firstHalfSorted.length)) {
        assignToOutput.accept(secondHalfSorted[secondIndex]);
        secondIndex++;
        continue;
      }

      if (isGreatherOrEquals(secondIndex, secondHalfSorted.length)) {
        assignToOutput.accept(firstHalfSorted[firstIndex]);
        firstIndex++;
        continue;
      }

      var oneTerm = firstHalfSorted[firstIndex];
      var secondTerm = secondHalfSorted[secondIndex];

      if (oneTerm < secondTerm) {
        assignToOutput.accept(oneTerm);
        firstIndex++;
      } else {
        assignToOutput.accept(secondTerm);
        secondIndex++;
      }
    }

    return outputSorted;
  }

  private static boolean isGreatherOrEquals (int i, int j) {
    return i >= j;
  }

  private static int[] copyAndSort (int[] unsorted, int start, int end) {
    return sort(Arrays.copyOfRange(unsorted, start, end));
  }

}

Na segunda implementação, fiz algumas modificações importantes.

1. Eu não quero ter sempre que lembrar de ter que fazer currying com os métodos sort e Arrays::copyOfRange. Neste caso, extrai-se um método em separado para simplificar as chamadas. Então só chamo aqui MergeSort::copyAndSort que já irá fazer as duas operações para mim de uma vez. Ainda sim é uma chamada recursiva.
2. Uso um lambda para simplificar a inclusão de um elemento para um array destino. Neste caso, basta eu chamar este lambda para adicionar. Não preciso mais fazer target[i], simplificando minha carga cognitiva ao escrever o código.

Porém, esta segunda implementação não tira vantagem que a biblioteca padrão do java tem.

Terceira Implementação: usando collections.

public class MergeSort {

  private static List<Integer> sort (List<Integer> unsorted) {
    var size = unsorted.size();

    if (size <= 2) {
      // simple reordering, behind the scenes is a merge sort
      return unsorted.stream()
                     .sorted(Comparator.naturalOrder())
                     .collect(Collectors.toList());
    }

    var halfSize = size / 2;

    var firstHalfSorted = sort(unsorted.subList(0, halfSize));
    var secondHalfSorted = sort(unsorted.subList(halfSize, size));

    var finalList = new ArrayList<Integer>();

    for (int i = 0; i < size; i++) {
      if (firstHalfSorted.isEmpty()) {
        finalList.addAll(secondHalfSorted);
        break;
      } else if (secondHalfSorted.isEmpty()) {
        finalList.addAll(firstHalfSorted);
        break;
      } else if (firstHalfSorted.get(0) < secondHalfSorted.get(0)) {
        finalList.add(firstHalfSorted.remove(0));
      } else {
        finalList.add(secondHalfSorted.remove(0));
      }
    }

    return finalList;
  }

  public static int[] sort (int[] unsorted) {
    var list = Arrays.stream(unsorted).boxed().toList();
    var sortedList = sort(list);

    return sortedList.stream().mapToInt(x -> x).toArray();
  }


}

Neste caso aqui, a manipulação de fato irá acontecer em cima de um ArrayList. O método publico sort irá apenas receber um int[], convertê-lo em List<Integer> e repassa-lo ao método privado.

O resultado será convertido de volta para um int[] e retornado para o caller. Este processo de unboxing é feito através de uma função de identidade (x -> x) que vai converter um Stream<Integer> para um IntStream.

IMPORTANTE: Streams usam Generics para tipagem interna, sendo assim, uma Stream convencional não suporta tipos primitivos, fazendo-se necessário fazer o processo de boxing/unboxing do tipo.

No caso, podemos nos permitir a fazer uma leve trapaça aqui:

if (size <= 2) {
      // simple reordering, behind the scenes is a merge sort
      return unsorted.stream()
                     .sorted(Comparator.naturalOrder())
                     .collect(Collectors.toList());
    }

A trapaça se dá pelo fato de que, por baixo dos panos, os métodos de ordenação no Java implementam MergeSort. Nas versões mais modernas eles implementam uma variação chamada TimSort que é mais eficiente que o MergeSort per si.

Como temos apenas dois itens, utilizando este método já vai cair naturalmente no caso base do método de ordenação da biblioteca padrão.

O restante da diferença então se dá em utilizar ArrayLists para realizar a manipulação do Array. Aqui eu tenho que me preocupar menos com índices, me preocupando apenas com o tamanho de cada um dos elementos e realizando a remoção direta de cada um dos ArrayLists resultantes, como uma stack.

for (int i = 0; i < size; i++) {
      if (firstHalfSorted.isEmpty()) {
        finalList.addAll(secondHalfSorted);
        break;
      } else if (secondHalfSorted.isEmpty()) {
        finalList.addAll(firstHalfSorted);
        break;
      } else if (firstHalfSorted.get(0) < secondHalfSorted.get(0)) {
        finalList.add(firstHalfSorted.remove(0));
      } else {
        finalList.add(secondHalfSorted.remove(0));
      }
    }

Neste caso, tenho uma otimização final em que, se um dos arrays ficou vazio, ele pega todo o restante dos outros elementos e adiciona direto no array final, adiantando todo o processo.

Concluindo.

Esta implementação pode ser melhorada em muito mais ordens! Recomendo experimentar em cima disso.

O repositório com a implementação e o histórico se encontram aqui:
https://github.com/EronAlves1996/estruturas-de-dados