Class 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 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

      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 specified Comparator.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • IterativeMergeSort

        private IterativeMergeSort()
    • 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 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,
                                                   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 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.