Package org.apache.pdfbox.util
Class IterativeMergeSort
- java.lang.Object
-
- org.apache.pdfbox.util.IterativeMergeSort
-
public final class IterativeMergeSort extends java.lang.Object
This class provides an iterative (bottom-up) implementation of the MergeSort algorithm for any generic Java object which implements aComparator
.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
All Methods Static Methods Concrete Methods Modifier and Type Method Description private static <T> void
iterativeMergeSort(T[] arr, java.util.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, java.util.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(java.util.List<T> list, java.util.Comparator<? super T> cmp)
Sorts this list according to the order induced by the specifiedComparator
.
-
-
-
Method Detail
-
sort
public static <T> void sort(java.util.List<T> list, java.util.Comparator<? super T> cmp)
Sorts this list according to the order induced by the specifiedComparator
.- 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, java.util.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, java.util.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 dataaux
- Array containing copy of source data to be sortedfrom
- 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.
-
-