Package org.apache.pdfbox.util
Class IterativeMergeSort
java.lang.Object
org.apache.pdfbox.util.IterativeMergeSort
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 -
Method Summary
Modifier and TypeMethodDescriptionprivate 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 specifiedComparator
.
-
Constructor Details
-
IterativeMergeSort
private IterativeMergeSort()
-
-
Method Details
-
sort
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
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 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.
-