private SortableType[] getSortedTypes() {
    // size is pessimistic; doesn't include arrays
    SortableType[] sortableTypes = new SortableType[contentsOut.typeIds.size];
    for (int i = 0; i < dexes.length; i++) {
      readSortableTypes(sortableTypes, dexes[i], indexMaps[i]);
    }

    /*
     * Populate the depths of each sortable type. This makes D iterations
     * through all N types, where 'D' is the depth of the deepest type. For
     * example, the deepest class in libcore is Xalan's KeyIterator, which
     * is 11 types deep.
     */
    while (true) {
      boolean allDone = true;
      for (SortableType sortableType : sortableTypes) {
        if (sortableType != null && !sortableType.isDepthAssigned()) {
          allDone &= sortableType.tryAssignDepth(sortableTypes);
        }
      }
      if (allDone) {
        break;
      }
    }

    // Now that all types have depth information, the result can be sorted
    Arrays.sort(sortableTypes, SortableType.NULLS_LAST_ORDER);

    // Strip nulls from the end
    int firstNull = Arrays.asList(sortableTypes).indexOf(null);
    return firstNull != -1 ? Arrays.copyOfRange(sortableTypes, 0, firstNull) : sortableTypes;
  }
Returns the union of classes from both files, sorted in order such that a class is always
preceded by its supertype and implemented interfaces.
android/android_framework/dex-maker/src/main/java/com/android/dx/merge/DexMerger.java