com.sl.algorithms.sort.generalpurpose.merge

Class TopDownMergeSort<T extends java.lang.Comparable>

java.lang.Object

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

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

All Implemented Interfaces:

BaseInterface<T>, Constants, SortingEngine<T>

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

TopDownMergeSort recursively splits the array into sub-lists and merges them 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
TopDownMergeSort()

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

TopDownMergeSort

public TopDownMergeSort()

Method Detail

sort

public void sort(T[] objects)

Steps:
(0) if list is of size=1, return as is (i.e. base case).
(1) partition the array into to a cluster of single units (divide).
(2) sort adjacent units as a pair (conquer).
(3) merge adjacent unit (combine).
(4) repeat (2) and (3) till all units are merged.

Note: The copy-back step is avoided by alternating the direction of merge, during each recursion.

sortList

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