Mergesort using ArrayList in Java with example

So here is another sorting algorithm, “Merge Sort” which I have implemented it using ArrayList.

MergeSort follows the Divide and Conquer paradigm.

Divide part divides an unsorted array into 2 unsorted arrays till further division is not possible i.e there is only 1 element per array. So we need to divide an array of N element into N arrays of size 1 (Virtually).

Conquer part join 2 divided arrays into one array which is sorted. So we need to merge element from N array to 1 array having all element in sorted order.

Diving the array will take O(log n) time and will create log n level of sub arrays.
Conquer part at each level will merge 2 sorted arrays which takes O(n) at each level.
So worst case time taken by merge sort is O(n log n).
Merge sort is not considered to be a memory efficient as we need an extra memory at each level of merging. As you can see in the implementation example that is given here it needs an extra temporary array called : mergedSortedArray to store the temp sorted element.

Here is the source code and project structure for the MergeSort.

 

Project Structure

ProjectExporer

 

MergeSort.java

package daa;

import java.util.ArrayList;

public class MergeSort {
	private ArrayList<Integer> inputArray;
	
	public ArrayList<Integer> getSortedArray() {
		return inputArray;
	}

	public MergeSort(ArrayList<Integer> inputArray){
		this.inputArray = inputArray;
	}
	
	public void sortGivenArray(){		
		divide(0, this.inputArray.size()-1);
	}
	
	public void divide(int startIndex,int endIndex){
		
		//Divide till you breakdown your list to single element
		if(startIndex<endIndex && (endIndex-startIndex)>=1){
			int mid = (endIndex + startIndex)/2;
			divide(startIndex, mid);
			divide(mid+1, endIndex);		
			
			//merging Sorted array produce above into one sorted array
			merger(startIndex,mid,endIndex);			
		}		
	}	
	
	public void merger(int startIndex,int midIndex,int endIndex){
		
		//Below is the mergedarray that will be sorted array Array[i-midIndex] , Array[(midIndex+1)-endIndex]
		ArrayList<Integer> mergedSortedArray = new ArrayList<Integer>();
		
		int leftIndex = startIndex;
		int rightIndex = midIndex+1;
		
		while(leftIndex<=midIndex && rightIndex<=endIndex){
			if(inputArray.get(leftIndex)<=inputArray.get(rightIndex)){
				mergedSortedArray.add(inputArray.get(leftIndex));
				leftIndex++;
			}else{
				mergedSortedArray.add(inputArray.get(rightIndex));
				rightIndex++;
			}
		}		
		
		//Either of below while loop will execute
		while(leftIndex<=midIndex){
			mergedSortedArray.add(inputArray.get(leftIndex));
			leftIndex++;
		}
		
		while(rightIndex<=endIndex){
			mergedSortedArray.add(inputArray.get(rightIndex));
			rightIndex++;
		}
		
		int i = 0;
		int j = startIndex;
		//Setting sorted array to original one
		while(i<mergedSortedArray.size()){
			inputArray.set(j, mergedSortedArray.get(i++));
			j++;
		}
	}
}

 

MainPractise.java

 

import java.util.ArrayList;
import daa.MergeSort;

public class MainPractise implements Cloneable {	
	
	public static void main(String[] args) {		
		
		ArrayList<Integer> unsortedArray = new ArrayList<Integer>();
		
		unsortedArray.add(8);
		unsortedArray.add(7);
		unsortedArray.add(6);
		unsortedArray.add(5);
		unsortedArray.add(4);
		unsortedArray.add(0);
		unsortedArray.add(2);	
		MergeSort ms = new MergeSort(unsortedArray);
		
		System.out.println("---------Initial Unsorted Array---------");
		for(int i:ms.getSortedArray()){
			System.out.print(i+" ");
		}
		

		ms.sortGivenArray();
		
		System.out.println("\n------------Sorted Array------------");
		for(int i:ms.getSortedArray()){
			System.out.print(i+" ");
		}
	}
}

 

Output:

———Initial Unsorted Array———
8  7  6  5  4  0  2
————Sorted Array————
0  2  4  5  6  7  8

You can have above code from GIT.

GitHub-Mark-32px https://github.com/Niravkumar-Patel/SnippetExampleRepo.git


 

Leave a Reply

Your email address will not be published. Required fields are marked *