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

- Takes the input array and BREAK/DIVIDE it into half.
- call the same BREAK/DIVIDE function on the smaller halves , again – RECURSIVE function, with a base condition of array.size =1
- array.size() = 1 counted as SORTED. now rebuilding.
- 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.
- 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

- Partitioning(array, startIndex, endIndex) // breaking into pieces
- 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)