net.sf.jsort.sort
Class MergeSort

java.lang.Object
  net.sf.jsort.sort.AbstractSort
      net.sf.jsort.sort.MergeSort

All Implemented Interfaces:

CompareSort, SortAlgorithm

Direct Known Subclasses:

MergeInsertSort

public class MergeSort
extends AbstractSort

This is a implementation of Merge sort algorithm.

This is one of the divide and conquer algorithm. The ideia is to split the array into two parts, sort each one and merge both into a single one. Each derived array is again divide, sorted and merged.

This is a recursive approach that let the worst case complexity a function of n * ln (n) or O(nln(n)).

Author:

Domingos Creado

See Also:

http://en.wikipedia.org/wiki/Mergesort

Constructor Summary

MergeSort()

Method Summary

protected void	mergeSort(java.lang.Object[] a, java.util.Comparator comparator, int start, int end) This is the main function of the algorithm.
void	sort(java.lang.Object[] list, java.util.Comparator comparator, int start, int end) Sort a specific range of the list, using the specified comparator.

Methods inherited from class net.sf.jsort.sort.AbstractSort

sort, sort, sort, sort, sort, sort, sort

Methods inherited from class java.lang.Object

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

Constructor Detail

MergeSort

public MergeSort()

Method Detail

sort

public void sort(java.lang.Object[] list,
                 java.util.Comparator comparator,
                 int start,
                 int end)

Description copied from interface: CompareSort

Sort a specific range of the list, using the specified comparator.

Specified by:

sort in interface CompareSort

Specified by:

sort in class AbstractSort

Parameters:

list - to be sort

mergeSort

protected void mergeSort(java.lang.Object[] a,
                         java.util.Comparator comparator,
                         int start,
                         int end)

This is the main function of the algorithm. It recursively split the array in the middle, call itself to sort the first sub-array, call itself again to sort the second half and call merge.

Be attention to the fact that it will only stop the recursion then the size of sub-array is 1.

The recursion is something like this:

T(n) = 2*T(n) + M(n)

The complexity is 2 times the complexity of this function with n/2 elements (the array is splited in the middle) plus 1 call to merge M(n).

As the complexity of M(n) is n then:

T(n) = 2*T(n/2) + n

With some assumptions:

• k = ln(n) and
• S(k) = T(2^k)

We will get:

T(n) = n * ln(n).

Parameters:

a - array to be sorted

comparator -

start - start position

end - end position