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)
    Author:
    Alistair Oldfield
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      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
    • 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.