public void mergeSort(int[] arr)
{
int n = arr.length;
int[] temp = new int[n];
divideThenMerge(arr, 0, n - 1, temp);
}
public void divideThenMerge(int[] arr, int start, int end, int[] temp)
{
if(start < end)
{
int middle = (start + end) / 2;
divideThenMerge(arr, start, middle, temp);
divideThenMerge(arr, middle + 1, end, temp);
merge(arr, start, middle, end, temp);
}
}
public void merge(int[] arr, int start, int middle, int end, int[] temp)
{
int index1 = start;
int index2 = middle + 1;
int tempIndex = start;
while(index1 <= middle && index2 <= end)
{
if(arr[index1] < arr[index2])
{
temp[tempIndex] = arr[index1];
index1++;
}
else
{
temp[tempIndex] = arr[index2];
index2++;
}
tempIndex++;
}
while(index1 <= middle)
{
temp[tempIndex] = arr[index1];
index1++;
tempIndex++;
}
while(index2 <= end)
{
temp[tempIndex] = arr[index2];
index2++;
tempIndex++;
}
for(int i = start; i <= end; i++)
{
arr[i] = temp[i];
}
}