## Tuesday, 6 January 2015

### Java Program to sort elements using Merge Sort Technique

 This a Java program which sorts all the elements using Merge Sort Technique. Merge sort is a divide and conquer technique , here the element list is divided into half and that halves are again divided into halves until only 2 elements left . Then compare those 2 elements , smallest one is kept first, repeat the same process until are the halves are sorted , and repeat the same process but in reverse order to unite the element list into one again.

See the animation below to understand ,

"Merge-sort-example" by Swfung8 - Own work. Licensed under CC BY-SA 3.0 via Wikimedia Commons.

PROGRAM :
```package codingcorner.in;

import java.util.Scanner;

public class MergeSort {
public static void main(String[] args) {
int list[] = new int;
int i, n;
Scanner scan = new Scanner(System.in);
System.out.print("How many numbers ? \t");
n = scan.nextInt();
System.out.print("\n\n");
for (i = 0; i < n; i++) {
System.out.print("Enter number " + (i + 1));
list[i] = scan.nextInt();
}
scan.close();
partition(list, 0, n - 1);
System.out.print("\n\nAfter merge sort:\n");
for (i = 0; i < n; i++) {
System.out.print("\t" + list[i]);
}
System.out.print("\n\n");
}

private static void partition(int[] list, int low, int high) {
int mid;

if (low < high) {
mid = (low + high) / 2;
partition(list, low, mid);
partition(list, mid + 1, high);
mergeSort(list, low, mid, high);
}

}

private static void mergeSort(int[] list, int low, int mid, int high) {
int i, midd, k, loww;
int[] temp = new int;
loww = low;
i = low;
midd = mid + 1;
while ((loww <= mid) && (midd <= high)) {
if (list[loww] <= list[midd]) {
temp[i] = list[loww];
loww++;
} else {
temp[i] = list[midd];
midd++;
}
i++;
}
if (loww > mid) {
for (k = midd; k <= high; k++) {
temp[i] = list[k];
i++;
}
} else {
for (k = loww; k <= mid; k++) {
temp[i] = list[k];
i++;
}
}

for (k = low; k <= high; k++) {
list[k] = temp[k];
}

}
}
```

OUTPUT :