net.sf.jsort.sort
Class MergeInsertSort

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

All Implemented Interfaces:

CompareSort, SortAlgorithm

public final class MergeInsertSort
extends MergeSort

This is a modified version of Merge sort algorithm, that change the sorting algorithm when sorting small pieces arrays.

The Merge sort guarantee the logarithm complexity, but the "constants" omitted by the complexity notation does not reveal that with small size arrays, the O(n^2) algorithms are faster.

So, this algorithm has a threshold to really start the merge sort algorithm. During the recursion, when the array gets below the threshold, the insert sort algorithm is used.

As there is a thresold, the complexity of the insert sort can be assumed as constant, letting the complexity of this algorithm O(n*ln(n)).

Author:

Domingos Creado

Constructor Summary

MergeInsertSort()

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.

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

sort

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

MergeInsertSort

public MergeInsertSort()

Method Detail

mergeSort

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

Description copied from class: MergeSort

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).

Overrides:

mergeSort in class MergeSort

Parameters:

a - array to be sorted

start - start position

end - end position