Merge sort on linkedlist
http://javabypatel.blogspot.in/2015/12/merge-sort-linked-list.html
https://www.cs.cmu.edu/~adamchik/15-121/lectures/Sorting%20Algorithms/code/MergeSort.java
X.
http://www.vogella.com/tutorials/JavaAlgorithmsMergesort/article.html
http://www.java2novice.com/java-sorting-algorithms/merge-sort/
X.
http://javahungry.blogspot.com/2013/06/java-sorting-program-code-merge-sort.html
It's stable.
http://www.vogella.com/tutorials/JavaAlgorithmsMergesort/article.html
public static void sort(Comparable[] a) {
Comparable[] aux = new Comparable[a.length];
sort(a, aux, 0, a.length-1);
assert isSorted(a);
}
http://www.sinbadsoft.com/blog/sorting-big-files-using-k-way-merge-sort/
It consists of two steps: first, split the file into small chunks that would fit in memory, load each chunk, sort it, and write it back on disk. Second, perform a k-way merge on all the sorted chunks to get the final result.
External Merge Sort
https://code.google.com/p/externalsortinginjava/source/browse/trunk/src/main/java/com/google/code/externalsorting/ExternalSort.java
http://exceptional-code.blogspot.com/2011/07/external-sorting-for-sorting-large.html
1. Start reading the input file from the beginning.
2. Read M (or less if number of entries remaining in the file is less than M) numbers from the file and store it into a temp buffer.
3. Sort (using any good sorting method - Quicksort, for example) the numbers in the buffer stored in step 2.
4. Create a temp file in disk and write out the sorted numbers from step 3 to this temp file. Save the name of the temp file.
5. Repeat step 2 to 4 until all numbers from the input file has been read, sorted, and written out to temp files.
6. Open all the temp files (and set the read pointer to the beginning of the files).
7. Find the minimum number from the set of numbers currently pointed to by the file read pointer.
8. Write the number to disk. (To increase efficiency you could write the number to a buffer first and then flush the buffer out to disk when the buffer is full. But modern I/O libraries should be doing this anyway for you).
9. Read another number from the file that contained the minimum number at step 7.
10. Repeat step 7 to 9 until all numbers from all the temp files have been processed, merged, and written out to disk
Mergesort using Fork/Join Framework
http://www.java-allandsundry.com/2012/08/mergesort-using-forkjoin-framework.html
http://www.oracle.com/technetwork/articles/java/fork-join-422606.html
https://github.com/cowtowncoder/java-merge-sort
http://www.geeksforgeeks.org/3-way-merge-sort/
Time Complexity: In case of 2-way Merge sort we get the equation: T(n) = 2T(n/2) + O(n)
Similarly, in case of 3-way Merge sort we get the equation: T(n) = 3T(n/3) + O(n)
By solving it using Master method, we get its complexity as O(n log 3n).. Although time complexity looks less compared to 2 way merge sort, the time taken actually may become higher because number of comparisons in merge function go higher
http://www.geeksforgeeks.org/binary-search-preferred-ternary-search/
http://javabypatel.blogspot.in/2015/12/merge-sort-linked-list.html
private
Node mergeSortLinkList(Node startNode){
//Break the list until list is null or only 1 element is present in List.
if
(startNode==
null
|| startNode.getNext()==
null
){
return
startNode;
}
//Break the linklist into 2 list.
//Finding Middle node and then breaking the Linled list in 2 parts.
//Now 2 list are, 1st list from start to middle and 2nd list from middle+1 to last.
Node middle = getMiddle(startNode);
Node nextOfMiddle = middle.getNext();
middle.setNext(
null
);
//Again breaking the List until there is only 1 element in each list.
Node left = mergeSortLinkList(startNode);
Node right = mergeSortLinkList(nextOfMiddle);
//Once complete list is divided and contains only single element,
//Start merging left and right half by sorting them and passing Sorted list further.
Node sortedList = mergeTwoListRecursive(left, right);
return
sortedList;
}
//Recursive Approach for Merging Two Sorted List
private
Node mergeTwoListRecursive(Node leftStart, Node rightStart){
if
(leftStart==
null
)
return
rightStart;
if
(rightStart==
null
)
return
leftStart;
Node temp=
null
;
if
(leftStart.getData()<rightStart.getData()){
temp=leftStart;
temp.setNext(mergeTwoListRecursive(leftStart.getNext(), rightStart));
}
else
{
temp=rightStart;
temp.setNext(mergeTwoListRecursive(leftStart, rightStart.getNext()));
}
return
temp;
}
private
Node getMiddle(Node startNode) {
if
(startNode==
null
){
return
startNode;
}
Node pointer1=startNode;
Node pointer2=startNode;
while
(pointer2!=
null
&& pointer2.getNext()!=
null
&& pointer2.getNext().getNext()!=
null
){
pointer1 = pointer1.getNext();
pointer2 = pointer2.getNext().getNext();
}
return
pointer1;
}
//Iterative Approach for Merging Two Sorted List
private
Node mergeTwoListIterative(Node leftStart, Node rightStart) {
Node merged=
null
;
Node temp=
null
;
//To keep track of last element, so that we don't need to iterate for adding the element at last of
//list when either LeftStart or rightStart is NULL.
Node lastAddedNode =
null
;
while
(leftStart!=
null
&& rightStart!=
null
){
if
(leftStart.getData()>rightStart.getData()){
temp =
new
Node(rightStart.getData());
rightStart=rightStart.getNext();
}
else
{
temp =
new
Node(leftStart.getData());
leftStart=leftStart.getNext();
}
if
(merged==
null
){
merged=temp;
}
else
{
lastAddedNode.setNext(temp);
}
lastAddedNode=temp;
}
if
(leftStart!=
null
){
lastAddedNode.setNext(leftStart);
}
else
{
lastAddedNode.setNext(rightStart);
}
return
merged;
}
public static void mergeSort(Comparable [ ] a)
{
Comparable[] tmp = new Comparable[a.length];
mergeSort(a, tmp, 0, a.length - 1);
}
private static void mergeSort(Comparable [ ] a, Comparable [ ] tmp, int left, int right)
{
if( left < right )
{
int center = (left + right) / 2;
mergeSort(a, tmp, left, center);
mergeSort(a, tmp, center + 1, right);
merge(a, tmp, left, center + 1, right);
}
}
private static void merge(Comparable[ ] a, Comparable[ ] tmp, int left, int right, int rightEnd )
{
int leftEnd = right - 1;
int k = left;
int num = rightEnd - left + 1;
while(left <= leftEnd && right <= rightEnd)
if(a[left].compareTo(a[right]) <= 0)
tmp[k++] = a[left++];
else
tmp[k++] = a[right++];
while(left <= leftEnd) // Copy rest of first half
tmp[k++] = a[left++];
while(right <= rightEnd) // Copy rest of right half
tmp[k++] = a[right++];
// Copy tmp back
for(int i = 0; i < num; i++, rightEnd--)
a[rightEnd] = tmp[rightEnd];
}
X.
http://www.vogella.com/tutorials/JavaAlgorithmsMergesort/article.html
http://www.java2novice.com/java-sorting-algorithms/merge-sort/
private int[] numbers;
private int[] helper;
private int number;
public void sort(int[] values) {
this.numbers = values;
number = values.length;
this.helper = new int[number];
mergesort(0, number - 1);
}
private void mergesort(int low, int high) {
// check if low is smaller then high, if not then the array is sorted
if (low < high) {
// Get the index of the element which is in the middle
int middle = low + (high - low) / 2;
// Sort the left side of the array
mergesort(low, middle);
// Sort the right side of the array
mergesort(middle + 1, high);
// Combine them both
merge(low, middle, high);
}
}
private void merge(int low, int middle, int high) {
// Copy both parts into the helper array
for (int i = low; i <= high; i++) {
helper[i] = numbers[i];
}
int i = low;
int j = middle + 1;
int k = low;
// Copy the smallest values from either the left or the right side back
// to the original array
while (i <= middle && j <= high) {
if (helper[i] <= helper[j]) {
numbers[k] = helper[i];
i++;
} else {
numbers[k] = helper[j];
j++;
}
k++;
}
// Copy the rest of the left side of the array into the target array
while (i <= middle) {
numbers[k] = helper[i];
k++;
i++;
}
}
X.
http://javahungry.blogspot.com/2013/06/java-sorting-program-code-merge-sort.html
public static int[] mergeSort(int [] list) { if (list.length <= 1) { return list; } // Split the array in half int[] first = new int[list.length / 2]; int[] second = new int[list.length - first.length]; System.arraycopy(list, 0, first, 0, first.length); System.arraycopy(list, first.length, second, 0, second.length); // Sort each half mergeSort(first); mergeSort(second); // Merge the halves together, overwriting the original array merge(first, second, list); return list; } private static void merge(int[] first, int[] second, int [] result) { // Merge both halves into the result array // Next element to consider in the first array int iFirst = 0; // Next element to consider in the second array int iSecond = 0; // Next open position in the result int j = 0; // As long as neither iFirst nor iSecond is past the end, move the // smaller element into the result. while (iFirst < first.length && iSecond < second.length) { if (first[iFirst] < second[iSecond]) { result[j] = first[iFirst]; iFirst++; } else { result[j] = second[iSecond]; iSecond++; } j++; } // copy what's left System.arraycopy(first, iFirst, result, j, first.length - iFirst); System.arraycopy(second, iSecond, result, j, second.length - iSecond); }
It's stable.
http://www.vogella.com/tutorials/JavaAlgorithmsMergesort/article.html
public static void sort(Comparable[] a) {
Comparable[] aux = new Comparable[a.length];
sort(a, aux, 0, a.length-1);
assert isSorted(a);
}
http://www.sinbadsoft.com/blog/sorting-big-files-using-k-way-merge-sort/
It consists of two steps: first, split the file into small chunks that would fit in memory, load each chunk, sort it, and write it back on disk. Second, perform a k-way merge on all the sorted chunks to get the final result.
External Merge Sort
https://code.google.com/p/externalsortinginjava/source/browse/trunk/src/main/java/com/google/code/externalsorting/ExternalSort.java
http://exceptional-code.blogspot.com/2011/07/external-sorting-for-sorting-large.html
1. Start reading the input file from the beginning.
2. Read M (or less if number of entries remaining in the file is less than M) numbers from the file and store it into a temp buffer.
3. Sort (using any good sorting method - Quicksort, for example) the numbers in the buffer stored in step 2.
4. Create a temp file in disk and write out the sorted numbers from step 3 to this temp file. Save the name of the temp file.
5. Repeat step 2 to 4 until all numbers from the input file has been read, sorted, and written out to temp files.
6. Open all the temp files (and set the read pointer to the beginning of the files).
7. Find the minimum number from the set of numbers currently pointed to by the file read pointer.
8. Write the number to disk. (To increase efficiency you could write the number to a buffer first and then flush the buffer out to disk when the buffer is full. But modern I/O libraries should be doing this anyway for you).
9. Read another number from the file that contained the minimum number at step 7.
10. Repeat step 7 to 9 until all numbers from all the temp files have been processed, merged, and written out to disk
Mergesort using Fork/Join Framework
http://www.java-allandsundry.com/2012/08/mergesort-using-forkjoin-framework.html
http://www.oracle.com/technetwork/articles/java/fork-join-422606.html
https://github.com/cowtowncoder/java-merge-sort
http://www.geeksforgeeks.org/3-way-merge-sort/
public
static
void
mergeSort3Way(Integer[] gArray)
{
// if array of size is zero returns null
if
(gArray ==
null
)
return
;
// creating duplicate of given array
Integer[] fArray =
new
Integer[gArray.length];
// copying alements of given array into
// duplicate array
for
(
int
i =
0
; i < fArray.length; i++)
fArray[i] = gArray[i];
// sort function
mergeSort3WayRec(fArray,
0
, gArray.length, gArray);
// copy back elements of duplicate array
// to given array
for
(
int
i =
0
; i < fArray.length; i++)
gArray[i] = fArray[i];
}
/* Performing the merge sort algorithm on the
given array of values in the rangeof indices
[low, high). low is minimum index, high is
maximum index (exclusive) */
public
static
void
mergeSort3WayRec(Integer[] gArray,
int
low,
int
high, Integer[] destArray)
{
// If array size is 1 then do nothing
if
(high - low <
2
)
return
;
// Splitting array into 3 parts
int
mid1 = low + ((high - low) /
3
);
int
mid2 = low +
2
* ((high - low) /
3
) +
1
;
// Sorting 3 arrays recursively
mergeSort3WayRec(destArray, low, mid1, gArray);
mergeSort3WayRec(destArray, mid1, mid2, gArray);
mergeSort3WayRec(destArray, mid2, high, gArray);
// Merging the sorted arrays
merge(destArray, low, mid1, mid2, high, gArray);
}
/* Merge the sorted ranges [low, mid1), [mid1,
mid2) and [mid2, high) mid1 is first midpoint
index in overall range to merge mid2 is second
midpoint index in overall range to merge*/
public
static
void
merge(Integer[] gArray,
int
low,
int
mid1,
int
mid2,
int
high,
Integer[] destArray)
{
int
i = low, j = mid1, k = mid2, l = low;
// choose smaller of the smallest in the three ranges
while
((i < mid1) && (j < mid2) && (k < high))
{
if
(gArray[i].compareTo(gArray[j]) <
0
)
{
if
(gArray[i].compareTo(gArray[k]) <
0
)
destArray[l++] = gArray[i++];
else
destArray[l++] = gArray[k++];
}
else
{
if
(gArray[j].compareTo(gArray[k]) <
0
)
destArray[l++] = gArray[j++];
else
destArray[l++] = gArray[k++];
}
}
// case where first and second ranges have
// remaining values
while
((i < mid1) && (j < mid2))
{
if
(gArray[i].compareTo(gArray[j]) <
0
)
destArray[l++] = gArray[i++];
else
destArray[l++] = gArray[j++];
}
// case where second and third ranges have
// remaining values
while
((j < mid2) && (k < high))
{
if
(gArray[j].compareTo(gArray[k]) <
0
)
destArray[l++] = gArray[j++];
else
destArray[l++] = gArray[k++];
}
// case where first and third ranges have
// remaining values
while
((i < mid1) && (k < high))
{
if
(gArray[i].compareTo(gArray[k]) <
0
)
destArray[l++] = gArray[i++];
else
destArray[l++] = gArray[k++];
}
// copy remaining values from the first range
while
(i < mid1)
destArray[l++] = gArray[i++];
// copy remaining values from the second range
while
(j < mid2)
destArray[l++] = gArray[j++];
// copy remaining values from the third range
while
(k < high)
destArray[l++] = gArray[k++];
}
Time Complexity: In case of 2-way Merge sort we get the equation: T(n) = 2T(n/2) + O(n)
Similarly, in case of 3-way Merge sort we get the equation: T(n) = 3T(n/3) + O(n)
By solving it using Master method, we get its complexity as O(n log 3n).. Although time complexity looks less compared to 2 way merge sort, the time taken actually may become higher because number of comparisons in merge function go higher
http://www.geeksforgeeks.org/binary-search-preferred-ternary-search/
int
ternarySearch(
int
arr[],
int
l,
int
r,
int
x)
{
if
(r >= l)
{
int
mid1 = l + (r - l)/3;
int
mid2 = mid1 + (r - l)/3;
// If x is present at the mid1
if
(arr[mid1] == x)
return
mid1;
// If x is present at the mid2
if
(arr[mid2] == x)
return
mid2;
// If x is present in left one-third
if
(arr[mid1] > x)
return
ternarySearch(arr, l, mid1-1, x);
// If x is present in right one-third
if
(arr[mid2] < x)
return
ternarySearch(arr, mid2+1, r, x);
// If x is present in middle one-third
return
ternarySearch(arr, mid1+1, mid2-1, x);
}
// We reach here when element is not present in array
return
-1;
}
Which of the above two does less comparisons in worst case?
From the first look, it seems the ternary search does less number of comparisons as it makes Log3n recursive calls, but binary search makes Log2n recursive calls. Let us take a closer look.
The following is recursive formula for counting comparisons in worst case of Binary Search.
From the first look, it seems the ternary search does less number of comparisons as it makes Log3n recursive calls, but binary search makes Log2n recursive calls. Let us take a closer look.
The following is recursive formula for counting comparisons in worst case of Binary Search.
T(n) = T(n/2) + 2, T(1) = 1
The following is recursive formula for counting comparisons in worst case of Ternary Search.
T(n) = T(n/3) + 4, T(1) = 1
In binary search, there are 2Log2n + 1 comparisons in worst case. In ternary search, there are 4Log3n + 1 comparisons in worst case.
Time Complexity for Binary search = 2clog2n + O(1) Time Complexity for Ternary search = 4clog3n + O(1)
Therefore, the comparison of Ternary and Binary Searches boils down the comparison of expressions 2Log3n and Log2n . The value of 2Log3n can be written as (2 / Log23) * Log2n . Since the value of (2 / Log23) is more than one, Ternary Search does more comparisons than Binary Search in worst case.