Package org.apache.pdfbox.util

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)

  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    private
    IterativeMergeSort()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    private static <T> void
    iterativeMergeSort(T[] arr, Comparator<? super T> cmp)
    Sorts the array using iterative (bottom-up) merge sort.
    private static <T> void
    merge(T[] arr, T[] aux, int from, int mid, int to, Comparator<? super T> cmp)
    Merges two sorted subarrays arr and aux into the order specified by cmp and places the ordered result back into into arr array.
    static <T> void
    sort(List<T> list, Comparator<? super T> cmp)
    Sorts this list according to the order induced by the specified Comparator.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • IterativeMergeSort

      private IterativeMergeSort()

  • 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.

    • iterativeMergeSort

      private static <T> void iterativeMergeSort(T[] arr, Comparator<? super T> cmp)
      Sorts the array using iterative (bottom-up) merge sort.
      Type Parameters:
      T - the class of the objects in the list
      Parameters:
      arr - the array of objects to be sorted.
      cmp - the comparator to determine the order of the list.

    • merge

      private static <T> void merge(T[] arr, T[] aux, int from, int mid, int to, Comparator<? super T> cmp)
      Merges two sorted subarrays arr and aux into the order specified by cmp and places the ordered result back into into arr array.
      Type Parameters:
      T -
      Parameters:
      arr - Array containing source data to be sorted and target for destination data
      aux - Array containing copy of source data to be sorted
      from - Start index of left data run so that Left run is arr[from : mid-1].
      mid - End index of left data run and start index of right run data so that Left run is arr[from : mid-1] and Right run is arr[mid : to]
      to - End index of right run data so that Right run is arr[mid : to]
      cmp - the comparator to determine the order of the list.