A merge sort works as follows:
- Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
- Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.
An example of merge sort. First divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally all the elements are sorted and merged. (Via Wikipedia)
import java.io.*;
class mergesort1 {
public static void simplemerge(int a[], int f, int s, int t) {
int i, j, k, w;
int temp[] = new int[a.length];
i = f;
j = s;
k = -1;
while (i <= s - 1 && j <= t) {
if (a[i] < a[j]) {
k++;
temp[k] = a[i];
i++;
} else {
k++;
temp[k] = a[j];
j++;
}
}
if (i > s - 1) {
for (w = j; w <= t; w++) {
k++;
temp[k] = a[w];
}
} else {
for (w = i; w <= s - 1; w++)
{
k++;
temp[k] = a[w];
}
}
for (w = 0; w <= k; w++)
a[f + w] = temp[w];
}
public static void mergesort(int a[], int left, int right) {
int mid;
if (left < right) {
mid = (left + right) / 2;
mergesort(a, left, mid);
mergesort(a, mid + 1, right);
simplemerge(a, left, mid + 1, right);
}
}
public static void main(String args[]) throws IOException {
System.out.println("enter the number of elements");
BufferedReader kbd = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(kbd.readLine());
int a[] = new int[n];
for (int i = 0; i <= n - 1; i++) {
System.out.println("enter elements" + (i + 1));
a[i] = Integer.parseInt(kbd.readLine());
}
mergesort(a, 0, n - 1);
for (int i = 0; i <= n - 1; i++)
System.out.println(a[i]);
}
}
/*
OUTPUT:
enter the number of elements
4
enter elements1
12
enter elements2
45
enter elements3
48
enter elements4
54
12
45
48
54
Process Exit...
*/