Class IterativeMergeSort

java.lang.Object
org.apache.pdfbox.util.IterativeMergeSort

public final class IterativeMergeSort extends Object
This class provides an iterative (bottom-up) implementation of the MergeSort algorithm for any generic Java object which implements a Comparator.

This implementation uses an iterative implementation approach over the more classical recursive approach in order to save the auxiliary space required by the call stack in recursive implementations.

Complexity:
  • Worst case time: O(n log n)
  • Best case time: O(n log n)
  • Average case time: O(n log n)
  • Space: O(n log n)
Author:
Alistair Oldfield
  • Method Details

    • sort

      public static <T> void sort(List<T> list, Comparator<? super T> cmp)
      Sorts this list according to the order induced by the specified Comparator.
      Type Parameters:
      T - the class of the objects in the list
      Parameters:
      list - the list to be sorted.
      cmp - the comparator to determine the order of the list.