This post originated from an RSS feed registered with Java Buzz
by instanceof java.
Original Post: Merge sort algorithm in java with example program
Feed Title: Instance Of Java
Feed URL: http://feeds.feedburner.com/blogspot/TXghwE
Feed Description: Instance of Java. A place where you can learn java in simple way each and every topic covered with many points and sample programs.
Merge sort one of the recursive sorting algorithm.
First divide the list of unsorted elements in two two parts. left half and right half.
Divide the left part elements in to sub lists until it become single element.
Divide right half of array or list of elements in to sub lists until it becomes one element in list.
After dividing all elements in two parts in to single entity.
Merge the elements into two by comparing lesser element will be first. apply same at right half
Merge all the elements in the left part until it become single sorted list
Now we have two sorted parts.
Means two parts sorted in ascending order and smaller element will be in first position.
Compare fist elements of two parts , lesser one should be takes first place in new sorted list
New sorted list or array having only one element now.
Compare two lists elements and place in sorting order and merge it.
Finally we have all elements sorted.
Compared to remaining algorithms like selection sort, insertion sort and bubble sort merge sort works faster.
Lets see what will be the time complexity of merge sort algorithm.
Time complexity of merge sort algorithm:
1.Best case time complexity: O(n log (n)) 2.Average case time complexity: O(n log (n)) 3.Worst case time complexity: O(n log (n)) 4.Worst case space complexity: O(n)
Merge sort in java with explanation diagram
Program#1: Java program to implement merge sort algorithm data structure
package com.instanceofjava.mergesortalgorithm;
public class MergeSortAlgorithm {
private int[] resarray;
private int[] tempMergArray;
private int length;
public static void main(String a[]){
int[] inputArr ={6,42,2,32,15,8,23,4};
System.out.println("Before sorting");
for(int i:inputArr){
System.out.print(i);
System.out.print(" ");
}
MergeSortAlgorithm mergesortalg = new MergeSortAlgorithm();
mergesortalg.sort(inputArr);
System.out.println();
System.out.println("After sorting");
for(int i:inputArr){
System.out.print(i);
System.out.print(" ");
}
}
public void sort(int inputArray[]) {
this.resarray = inputArray;
this.length = inputArray.length;
this.tempMergArray = new int[length];
doMergeSort(0, length - 1);
}
private void doMergeSort(int lowerIndex, int higherIndex) {
if (lowerIndex < higherIndex) {
int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
//to sort left half of the array
doMergeSort(lowerIndex, middle);
// to sort right half of the array
doMergeSort(middle + 1, higherIndex);
//merge two halfs
mergehalfs(lowerIndex, middle, higherIndex);
}
}
private void mergehalfs(int lowerIndex, int middle, int higherIndex) {
Previous Topic
