package com.exuan.sort;
public class MergeSort {
/*
* Conceptually, a merge sort works as follows
* 1. If the list is of length 0 or 1, then it is already sorted. Otherwise:
* 2. Divide the unsorted list into two sublists of about half the size.
* 3. Sort each sublist recursively by re-applying the merge sort.
* 4. Merge the two sublists back into one sorted list.
*/
public static void main(String[] args)
{
int[] data = {49,38,65,97,76,13,27,49,55,4};
display(data);
mergeSort1(data, 0, data.length - 1);
//mergeSort2(data);
display(data);
}
/*
* ------------------------------------------------------------------
* 1. recursive
*/
static void mergeData1(int array[], int p, int q, int r)
{
int i,k;
int begin1, end1, begin2, end2;
int[] temp = new int[r - p + 1];
begin1= p;
end1 = q;
begin2 = q+1;
end2 = r;
k = 0;
while((begin1 <= end1)&&( begin2 <= end2))
{
if(array[begin1] < array[begin2])
{
temp[k] = array[begin1];
begin1++;
}
else
{
temp[k] = array[begin2];
begin2++;
}
k++;
}
while(begin1<=end1)
{
temp[k++] = array[begin1++];
}
while(begin2<=end2)
{
temp[k++] = array[begin2++];
}
for (i = 0; i <= (r - p); i++)
{
array[p+i] = temp[i];
}
}
static void mergeSort1(int array[], int first, int last)
{
int mid = 0;
if(first < last)
{
mid = (first+last)/2;
mergeSort1(array, first, mid);
mergeSort1(array, mid + 1,last);
mergeData1(array, first, mid, last);
}
}
/*
* 1. recursive
* ------------------------------------------------------------------
*/
/*
* ------------------------------------------------------------------
* 2. not recursive
*/
/*
* first is the start of the first sub sequence,
* second is the start of the second sub sequence,
* left_width is the length of the sub sequence
*/
private static void mergeData2(int[] data, int first, int second, int left_width)
{
int right_width;
/*
* if the length of second sub sequence is less than the first,
* for example {13,27,38,49,49,65,76,97},{4,55}
* then right_width is the actual length
*/
if(second + left_width - 1 >= data.length - 1)
{
right_width = data.length-second;
}
else
{
/*
* the length of second sub sequence is equal to the first
* for example {38,49,65,97},{13,27,49,76}
* right_width = left_width = 4
*/
right_width = left_width;
}
/*
* create a temp array that can store the sort result of the two sub sequences,
* so its size is 'left_width+right_width'
*/
int[] temp = new int[left_width+right_width];
int i = 0;
int j = 0;
/*
* i loop in the first sub sequence, j loop in the second sub sequence,
* we now start to merge the two sub sequences,
* this 'while' loop end when we reach one of the sub sequence' end
*/
while(i <= left_width - 1 && j <= right_width - 1)
{
/*
* if data in first sub sequence is less,
* we store it to the temp array,
* increase i
*/
if(data[first+i] <= data[second+j])
{
temp[i+j] = data[first+i];
i++;
}
else
{
/*
* if data in second sub sequence is less,
* we store it to the temp array,
* increase j
*/
temp[i+j] = data[second+j];
j++;
}
}
/*
* we reach the end of the second sub sequence,
* which means the the data in second sub sequence is less than some of the first,
* we then move the unsorted data in the first sub to right
*/
if(j == right_width)
{
for(int t = 0; t < left_width - i; t++)
{
data[first + i + j + t] = data[first + i + t];
}
}
/*
* copy the temp sorted data to our array
*/
for(int t = 0; t < i + j; t++)
{
data[first + t] = temp[t];
}
}
private static void mergeSort2(int[] data)
{
int step = 1;
/*
* we increase the step from 1 to data length - 1,
* divide the original sequence into several sub sequences,
* then loop to sort each sub sequence
*/
while(step < data.length)
{
/*
* first {49,38},{65,97},{76,13},{27,49},{55,4} to {38,49},{65,97},{13,76},{27,49},{4,55}
* the for loop will do merge each sub sequence,
* then {38,49,65,97},{13,76,27,49},{4,55} to {38,49,65,97},{13,27,49,76},{4,55}
* then {38,49,65,97,13,27,49,76},{4,55} to {13,27,38,49,49,65,76,97},{4,55}
* then {13,27,38,49,49,65,76,97,4,55} to {4,13,27,38,49,49,55,65,76,97}
*/
for(int i = 0; i <= data.length - step - 1; i += 2 * step)
{
mergeData2(data, i, i + step, step);
}
step *= 2;
}
}
/*
* 2. not recursive
* ------------------------------------------------------------------
*/
private static void display(int[] data)
{
for(int i = 0; i < data.length; i++)
{
System.out.print(data[i]);
if(i != data.length - 1)
{
System.out.print(",");
}
}
System.out.println();
}
}