Data Structure – Merge Sort

under divide and conquer algorithms in sort category, we are reaching to Merge Sort, which basically

  1. Takes the input array and BREAK/DIVIDE it into half.
  2. call the same BREAK/DIVIDE function on the smaller halves , again – RECURSIVE function, with a base condition of array.size =1
  3. array.size() = 1 counted as SORTED. now rebuilding.
  4. in the time of rebuilding process for the smaller chunk of data, we are using previous smaller chunk in each step, meaning, smaller sorted data as a result of last previous recursive call.
  5. and then rebuild the array after sorting the smaller previous parts.

NOTE: in this sorting algorithm, we need a copy of the array, in a merging process and that’s the tricky part.

 big picture:

we have two main function in Merge Sort

  1. Partitioning(array, startIndex, endIndex) // breaking into pieces
  2. Merging(array, startIndex, midIndex, endIndex) // sorting and rebuilding

/**
* breaking the array into smaller pieces, RECURSIVE happened here.
*
* @param arrSRC
* @param startIndex
* @param endIndex
*/
public void partitioning(int[] arrSRC, int startIndex, int endIndex) {

System.out.println("Begin Dividing/Breaking by this array...");
showContent(arrSRC, startIndex, endIndex);

if (endIndex - 1 == startIndex) {
System.out.println("Dividing/Breaking - into smaller chunk - found only one item in array, so it's counted as SORTED.");
return;
}

System.out.println("Dividing/Breaking - into smaller chunk - Finding Mid Index.");
int mid = (startIndex + endIndex) / 2;

System.out.printf("Dividing/Breaking - into smaller chunk -  startIndex: %d - endIndex: %d = midIndex:%d\n", startIndex, endIndex, mid);

partitioning(arrSRC, startIndex, mid);
partitioning(arrSRC, mid, endIndex);

doMerge(arrSRC, startIndex, mid, endIndex);

}

/**
* do the actual merge/build task.
*
* @param arrSrc
* @param startIndex
* @param mid
* @param endIndex
*/
private void doMerge(int[] arrSrc, int startIndex, int mid, int endIndex) {

//tricky partitioning in MERGE SORT since we need a semi-sorted array which was made in previous recursive function call.
System.out.println("Begin Conquering/ building array again...");

arrayCopy(arrSrc, tempArr, startIndex, endIndex);

int leftIndex = startIndex;
int rightIndex = mid;
int index = startIndex;

while (leftIndex < mid && rightIndex < endIndex) {
if (tempArr[leftIndex] <= tempArr[rightIndex]) {

arrSrc[index] = tempArr[leftIndex];
leftIndex++;

} else {
arrSrc[index] = tempArr[rightIndex];
rightIndex++;
}
index++;
}

while (leftIndex < mid) {
arrSrc[index] = tempArr[leftIndex];
leftIndex++;
index++;
}
while (rightIndex < endIndex) {
arrSrc[index] = tempArr[rightIndex];
rightIndex++;
index++;
}

System.out.print("Final Result ... \n\t ");
showContent(arrSrc, startIndex, endIndex);
System.out.println("");

}

Orders:

in the worst case scenario O(N x LogN), since it’s breaking the target into a smaller chunk. so it’s good for large unsorted data sets.

when to use?

when you want to do the sort in a multi-thread environment so every thread can do one part of sorting and then one manager thread can stick the parts together.

how to implement?


package com.navid.ds.practice.sorting.divideconqure;

/**
*
* @author Unknown_
*/
public class MergeSort {

public static int[] myArray = new int[]{10, 2, 5, 20, 90, 12, 31, 5};
private static int[] tempArr = null;

public MergeSort() {

tempArr = new int[myArray.length];

}

/**
* breaking the array into smaller pieces, RECURSIVE happened here.
*
* @param arrSRC
* @param startIndex
* @param endIndex
*/
public void partitioning(int[] arrSRC, int startIndex, int endIndex) {

System.out.println("Begin Dividing/Breaking by this array...");
showContent(arrSRC, startIndex, endIndex);

if (endIndex - 1 == startIndex) {
System.out.println("Dividing/Breaking - into smaller chunk - found only one item in array, so it's counted as SORTED.");
return;
}

System.out.println("Dividing/Breaking - into smaller chunk - Finding Mid Index.");
int mid = (startIndex + endIndex) / 2;

System.out.printf("Dividing/Breaking - into smaller chunk -  startIndex: %d - endIndex: %d = midIndex:%d\n", startIndex, endIndex, mid);

partitioning(arrSRC, startIndex, mid);
partitioning(arrSRC, mid, endIndex);

doMerge(arrSRC, startIndex, mid, endIndex);

}

/**
* do the actual merge/build task.
*
* @param arrSrc
* @param startIndex
* @param mid
* @param endIndex
*/
private void doMerge(int[] arrSrc, int startIndex, int mid, int endIndex) {

//tricky partitioning in MERGE SORT since we need a semi-sorted array which was made in previous recursive function call.
System.out.println("Begin Conquering/ building array again...");

arrayCopy(arrSrc, tempArr, startIndex, endIndex);

int leftIndex = startIndex;
int rightIndex = mid;
int index = startIndex;

while (leftIndex < mid && rightIndex < endIndex) {
if (tempArr[leftIndex] <= tempArr[rightIndex]) {

arrSrc[index] = tempArr[leftIndex];
leftIndex++;

} else {
arrSrc[index] = tempArr[rightIndex];
rightIndex++;
}
index++;
}

while (leftIndex < mid) {
arrSrc[index] = tempArr[leftIndex];
leftIndex++;
index++;
}
while (rightIndex < endIndex) {
arrSrc[index] = tempArr[rightIndex];
rightIndex++;
index++;
}

System.out.print("Final Result ... \n\t ");
showContent(arrSrc, startIndex, endIndex);
System.out.println("");

}

/**
* This array Copy method is just an effort to expose the
*
* @param arrSrc
* @param arrDest
* @param lowerIndex
* @param higherIndex
*/
public void arrayCopy(int[] arrSrc, int[] arrDest, int lowerIndex, int higherIndex) {

for (int i = lowerIndex; i < higherIndex; i++) {
arrDest[i] = arrSrc[i];
}

}

public void showContent(int[] arr, int start, int end) {

System.out.print("[ ");
for (int i = start; i < end; i++) {
System.out.printf("%d, ", arr[i]);

}
System.out.println(" ]");
}

public static void main(String[] args) {

MergeSort ms = new MergeSort();

ms.partitioning(myArray, 0, myArray.length);

}

}

 

 

output

run:
Begin Dividing/Breaking by this array...
[ 10, 2, 5, 20, 90, 12, 31, 5,  ]
Dividing/Breaking - into smaller chunk - startIndex: 0 - endIndex: 8 = midIndex:4
Begin Dividing/Breaking by this array...
[ 10, 2, 5, 20,  ]
Dividing/Breaking - into smaller chunk - startIndex: 0 - endIndex: 4 = midIndex:2
Begin Dividing/Breaking by this array...
[ 10, 2,  ]
Dividing/Breaking - into smaller chunk - startIndex: 0 - endIndex: 2 = midIndex:1
Begin Dividing/Breaking by this array...
[ 10,  ]
Dividing/Breaking - into smaller chunk - found only one item in array, so it's counted as SORTED.
Begin Dividing/Breaking by this array...
[ 2,  ]
Dividing/Breaking - into smaller chunk - found only one item in array, so it's counted as SORTED.
Begin Conquering/ building array again...
Final Result ... 
     [ 2, 10,  ]

Begin Dividing/Breaking by this array...
[ 5, 20,  ]
Dividing/Breaking - into smaller chunk - startIndex: 2 - endIndex: 4 = midIndex:3
Begin Dividing/Breaking by this array...
[ 5,  ]
Dividing/Breaking - into smaller chunk - found only one item in array, so it's counted as SORTED.
Begin Dividing/Breaking by this array...
[ 20,  ]
Dividing/Breaking - into smaller chunk - found only one item in array, so it's counted as SORTED.
Begin Conquering/ building array again...
Final Result ... 
     [ 5, 20,  ]

Begin Conquering/ building array again...
Final Result ... 
     [ 2, 5, 10, 20,  ]

Begin Dividing/Breaking by this array...
[ 90, 12, 31, 5,  ]
Dividing/Breaking - into smaller chunk - startIndex: 4 - endIndex: 8 = midIndex:6
Begin Dividing/Breaking by this array...
[ 90, 12,  ]
Dividing/Breaking - into smaller chunk - startIndex: 4 - endIndex: 6 = midIndex:5
Begin Dividing/Breaking by this array...
[ 90,  ]
Dividing/Breaking - into smaller chunk - found only one item in array, so it's counted as SORTED.
Begin Dividing/Breaking by this array...
[ 12,  ]
Dividing/Breaking - into smaller chunk - found only one item in array, so it's counted as SORTED.
Begin Conquering/ building array again...
Final Result ... 
     [ 12, 90,  ]

Begin Dividing/Breaking by this array...
[ 31, 5,  ]
Dividing/Breaking - into smaller chunk - startIndex: 6 - endIndex: 8 = midIndex:7
Begin Dividing/Breaking by this array...
[ 31,  ]
Dividing/Breaking - into smaller chunk - found only one item in array, so it's counted as SORTED.
Begin Dividing/Breaking by this array...
[ 5,  ]
Dividing/Breaking - into smaller chunk - found only one item in array, so it's counted as SORTED.
Begin Conquering/ building array again...
Final Result ... 
     [ 5, 31,  ]

Begin Conquering/ building array again...
Final Result ... 
     [ 5, 12, 31, 90,  ]

Begin Conquering/ building array again...
Final Result ... 
     [ 2, 5, 5, 10, 12, 20, 31, 90,  ]

BUILD SUCCESSFUL (total time: 0 seconds)

 

Advertisements

One thought on “Data Structure – Merge Sort

  1. Pingback: Data Structure – Sorting Algorithms in Java | Navid's Thoughts

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s