Top Description Constructors Methods
org.apache.pdfbox.util

public final Class IterativeMergeSort

extends Object
Class Inheritance
Imports
java.util.Comparator, .List, .ListIterator
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:
Author
Alistair Oldfield

Constructor Summary

AccessConstructor and Description
private
IterativeMergeSort()

Method Summary

Modifier and TypeMethod and Description
private static <
the class of the objects in the list
T> void
iterativeMergeSort(T[]
the array of objects to be sorted.
arr, Comparator<? super T>
the comparator to determine the order of the list.
cmp)

Sorts the array using iterative (bottom-up) merge sort.

private static <T> void
merge(T[]
Array containing source data to be sorted and target for destination data
arr, T[]
Array containing copy of source data to be sorted
aux, int
Start index of left data run so that Left run is arr[from : mid-1].
from, int
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]
mid, int
End index of right run data so that Right run is arr[mid : to]
to, Comparator<? super T>
the comparator to determine the order of the list.
cmp)

Merges two sorted subarrays arr and aux into the order specified by cmp and places the ordered result back into into arr array.

public static <
the class of the objects in the list
T> void
sort(List<T>
the list to be sorted.
list, Comparator<? super T>
the comparator to determine the order of the list.
cmp)

Sorts this list according to the order induced by the specified Comparator.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Constructor Detail

IterativeMergeSortback to summary
private IterativeMergeSort()

Method Detail

iterativeMergeSortback to summary
private static <T> void iterativeMergeSort(T[] arr, Comparator<? super T> cmp)

Sorts the array using iterative (bottom-up) merge sort.

Parameters
<T>
the class of the objects in the list
arr:T[]

the array of objects to be sorted.

cmp:Comparator<? super T>

the comparator to determine the order of the list.

mergeback to summary
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.

Parameters
arr:T[]

Array containing source data to be sorted and target for destination data

aux:T[]

Array containing copy of source data to be sorted

from:int

Start index of left data run so that Left run is arr[from : mid-1].

mid:int

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:int

End index of right run data so that Right run is arr[mid : to]

cmp:Comparator<? super T>

the comparator to determine the order of the list.

sortback to summary
public static <T> void sort(List<T> list, Comparator<? super T> cmp)

Sorts this list according to the order induced by the specified Comparator.

Parameters
<T>
the class of the objects in the list
list:List<T>

the list to be sorted.

cmp:Comparator<? super T>

the comparator to determine the order of the list.

Annotations
@SuppressWarnings:unchecked, rawtypes