private void doPrepare() {
      Timer timer = Timer.start();

      LOGGER.debug("Sorting long long multimap...");
      long[] sortedKeys = keys.toArray();

      // this happens in a worker thread, but it's OK to use parallel sort because
      // all other threads will block while we prepare the multimap.
      Arrays.parallelSort(sortedKeys);

      // after sorting keys, sort values by iterating through each unordered key/value pair and
      // using binary search to find where to insert the result in sorted values.
      long[] sortedValues = new long[sortedKeys.length];
      int from = 0;
      while (from < keys.size()) {
        long key = keys.get(from);
        int to = Arrays.binarySearch(sortedKeys, key);
        if (to < 0) {
          throw new IllegalStateException("Key not found: " + key);
        }
        // skip back to the first entry for this key
        while (to >= 0 && sortedKeys[to] == key) {
          to--;
        }
        // skip ahead past values we've already added for this key
        do {
          to++;
        } while (sortedValues[to] != 0);
        while (from < keys.size() && keys.get(from) == key) {
          sortedValues[to++] = values.get(from++);
        }
      }
      keys.buffer = sortedKeys;
      values.buffer = sortedValues;
      LOGGER.debug("Sorted long long multimap {}", timer.stop());
    }
Sort the keys and values arrays by key
planetiler-core/src/main/java/com/onthegomap/planetiler/collection/LongLongMultimap.java