Homework SourseThe implementation for Merge sort given in Section 74 takes
Solution
Linked List approach:-
package linkedlist.singly;
public class SortLinkedList {
Node startNode;
public static void main(String[] args) {
new SortLinkedList();
}
public SortLinkedList() {
Node node1 = new Node(10);
Node node2 = new Node(1);
Node node3 = new Node(-2);
Node node4 = new Node(8);
Node node5 = new Node(9);
Node node6 = new Node(10);
Node node7 = new Node(1);
node1.setNext(node2);
node2.setNext(node3);
node3.setNext(node4);
node4.setNext(node5);
node5.setNext(node6);
node6.setNext(node7);
startNode = node1;
Node sortedStartNode = mergeSortLinkList(startNode);
printLinkList(sortedStartNode);
}
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;
}
private void printLinkList(Node startNode) {
Node temp = startNode;
while(temp!=null){
System.out.print(temp.getData() + \" \");
temp = temp.getNext();
}
}
}
Array Logic -
class MergeSort
{
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
int L[] = new int [n1];
int R[] = new int [n2];
/*Copy data to temp arrays*/
for (int i=0; i<n1; ++i)
L[i] = arr[l + i];
for (int j=0; j<n2; ++j)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarry array
int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of L[] if any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
// Main function that sorts arr[l..r] using
// merge()
void sort(int arr[], int l, int r)
{
if (l < r)
{
// Find the middle point
int m = (l+r)/2;
// Sort first and second halves
sort(arr, l, m);
sort(arr , m+1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + \" \");
System.out.println();
}
// Driver method
public static void main(String args[])
{
int arr[] = {12, 11, 13, 5, 6, 7};
System.out.println(\"Given Array\");
printArray(arr);
MergeSort ob = new MergeSort();
ob.sort(arr, 0, arr.length-1);
System.out.println(\"\ Sorted array\");
printArray(arr);
}
}
Conclusion related to running time -> Mergesort works even better on linked lists than it does on arrays. It avoids the need for the auxiliary space, and becomes a simple, reliably O(N log N) sorting algorithm. And as an added bonus, it\'s stable too.
