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
MergeSort.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
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:
|
1 2 3 4 |
---------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.
https://github.com/Niravkumar-Patel/SnippetExampleRepo.git