com.sl.algorithms.sort.generalpurpose.merge

Class BottomUpMergeSort<T extends java.lang.Comparable>

java.lang.Object

com.sl.algorithms.sort.generalpurpose.merge.MergeSort<T>

com.sl.algorithms.sort.generalpurpose.merge.BottomUpMergeSort<T>

All Implemented Interfaces:

BaseInterface<T>, Constants, SortingEngine<T>

public class BottomUpMergeSort<T extends java.lang.Comparable>
extends MergeSort<T>

BottomUpMergeSort treats the input array as a cluster of sub-lists and iteratively merges them back and forth b/n 2 buffers to produce a sorted list.

See Also:

MergeSort

Field Summary

Fields inherited from interface com.sl.algorithms.core.interfaces.base.Constants

ARRAY_IS_EMPTY, DATA_TYPE_NOT_SUPPORTED_YET, DECIMAL_RADIX, DELIMITER_COMMA, ELEMENT_NOT_FOUND, LIST_IS_EMPTY, OPERATION_NOT_SUPPORTED_YET

Constructor Summary

Constructors

Constructor and Description
BottomUpMergeSort()

Method Summary

Modifier and Type	Method and Description
void	sort(T[] objects) Steps: (0) if list is of size=1, return as is (i.e.
ListNode<T>	sortList(ListNode<T> head)

Methods inherited from class com.sl.algorithms.sort.generalpurpose.merge.MergeSort

merge

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface com.sl.algorithms.core.interfaces.base.BaseInterface

checkArray, checkIntArray, checkList

Constructor Detail

BottomUpMergeSort

public BottomUpMergeSort()

Method Detail

sort

public void sort(T[] objects)

Steps:
(0) if list is of size=1, return as is (i.e. base case).
(1) pick sub-lists of size 1 and build bottom-up with width increasing in multiples of 2.
(2) sort adjacent units as a pair (conquer).
(3) iterate till entire width is sorted.

Note: The copy-back step is explicitly required in each iteration to incrementally sort the input array.

sortList

public ListNode<T> sortList(ListNode<T> head)