mergesort java

1public static void mergeSort(int[] a, int n) {
2    if (n < 2) {
3        return;
4    }
5    int mid = n / 2;
6    int[] l = new int[mid];
7    int[] r = new int[n - mid];
8 
9    for (int i = 0; i < mid; i++) {
10        l[i] = a[i];
11    }
12    for (int i = mid; i < n; i++) {
13        r[i - mid] = a[i];
14    }
15    mergeSort(l, mid);
16    mergeSort(r, n - mid);
17 
18    merge(a, l, r, mid, n - mid);
19}
20
21public static void merge(
22  int[] a, int[] l, int[] r, int left, int right) {
23 
24    int i = 0, j = 0, k = 0;
25    while (i < left && j < right) {
26        if (l[i] <= r[j]) {
27            a[k++] = l[i++];
28        }
29        else {
30            a[k++] = r[j++];
31        }
32    }
33    while (i < left) {
34        a[k++] = l[i++];
35    }
36    while (j < right) {
37        a[k++] = r[j++];
38    }
39}

1public static void mergeSort(int[] a, int n) {
2    if (n < 2) {
3        return;
4    }
5    int mid = n / 2;
6    int[] l = new int[mid];
7    int[] r = new int[n - mid];
8 
9    for (int i = 0; i < mid; i++) {
10        l[i] = a[i];
11    }
12    for (int i = mid; i < n; i++) {
13        r[i - mid] = a[i];
14    }
15    mergeSort(l, mid);
16    mergeSort(r, n - mid);
17 
18    merge(a, l, r, mid, n - mid);
19}
20

1public static void merge(
2  int[] a, int[] l, int[] r, int left, int right) {
3  
4    int i = 0, j = 0, k = 0;
5    while (i < left && j < right) {
6        if (l[i] <= r[j]) {
7            a[k++] = l[i++];
8        }
9        else {
10            a[k++] = r[j++];
11        }
12    }
13    while (i < left) {
14        a[k++] = l[i++];
15    }
16    while (j < right) {
17        a[k++] = r[j++];
18    }
19}
20

1import java.util.Random;
2import java.util.Scanner;
3
4public class MergeSort {
5    public static void main(String[] argh){
6        Scanner scanner  = new Scanner(System.in);
7        System.out.println("Enter the size of you victor: ");
8        int size = scanner.nextInt();
9        int[] unSortedArr = new int[size];
10        unSortedArr = enterRandomValues(unSortedArr);
11        int[] sortedARR = loop(unSortedArr);
12        print(sortedARR);
13    }
14    public static int[] loop(int[] unSortedArr){
15        for(int start = 0 ; start < unSortedArr.length ; ++start){
16            int minIndex = findTheMiniIndex(unSortedArr,start);
17            swap(unSortedArr,minIndex,start);
18        }
19
20        return unSortedArr ;
21    }
22
23    public static int findTheMiniIndex(int[] arr, int start){
24        int index = start;
25        for(int i = start+1 ; i < arr.length ; ++i){
26            if(arr[index]>arr[i]){
27                index = i ;
28            }
29        }
30
31        return index;
32    }
33
34    public static void swap(int[] swapValOfArr,int minIndex,int start){
35        int temp = swapValOfArr[minIndex];
36        swapValOfArr[minIndex]= swapValOfArr[start]  ;
37        swapValOfArr[start] = temp ;
38
39    }
40
41    public static void print(int[] sorteArr){
42        for(int i = 0 ; i < sorteArr.length ; ++i) {
43            System.out.println(sorteArr[i]);
44        }
45    }
46
47    public static int[] enterRandomValues(int[] unSortedArr){
48        Random random = new Random();
49        for(int i = 0 ; i< unSortedArr.length; ++i){
50            unSortedArr[i] =random.nextInt(1000);
51        }
52        return unSortedArr;
53    }
54}
55

1public class JavaMergeSort
2{
3   void sorting(int[] num, int left, int main, int right)
4   {
5      // finding size of two sub arrays
6      int list1 = main - left + 1;
7      int list2 = right - main;
8      // creating temporary array
9      int[] L = new int[list1];
10      int[] R = new int[list2];
11      // copying data to temporary array
12      for(int a = 0; a < list1; ++a)
13         L[a] = num[left + a];
14      for(int b = 0; b < list2; ++b)
15         R[b] = num[main + 1+ b];
16      // existing index of first and second sub array
17      int p = 0, q = 0;
18      // existing index of merged sub array
19      int r = left;
20      while(p < list1 && q < list2)
21      {
22         if(L[p] <= R[q])
23         {
24            num[r] = L[p];
25            p++;
26         }
27         else
28         {
29            num[r] = R[q];
30            q++;
31         }
32         r++;
33      }
34      // copying remaining elements of L[] array
35      while(p < list1)
36      {
37         num[r] = L[p];
38         p++;
39         r++;
40      }
41      // copying remaining elements of R[] array
42      while(q < list2)
43      {
44         num[r] = R[q];
45         q++;
46         r++;
47      }
48   }
49   // function that sorts
50   void sort(int[] arrNum, int l, int r)
51   {
52      if(l < r)
53      {
54         // finding middle point
55         int m = (l + r) / 2;
56         // sorting first and second list
57         sort(arrNum, l, m);
58         sort(arrNum , m+1, r);
59         // merging sorted list
60         sorting(arrNum, l, m, r);
61      }
62   }
63   // display array
64   static void displayArray(int[] arr)
65   {
66      int number = arr.length;
67      for(int a = 0; a < number; ++a)
68         System.out.print(arr[a] + " ");
69      System.out.println();
70   }
71   public static void main(String[] args)
72   {
73      int[] arrNumbers = {33, 00, 55, 11, 22, 44};
74      System.out.println("Before sorting - ");
75      displayArray(arrNumbers);
76      JavaMergeSort obj = new JavaMergeSort();
77      obj.sort(arrNumbers, 0, arrNumbers.length - 1);
78      System.out.println("\nAfter sorting - ");
79      displayArray(arrNumbers);
80   }
81}

1public class MergeSort
2{
3public static void main(String[] args)
4{
5int i;
6int values[] = new int[11];
7for(i=0; i<values.length; i++) { values[i]=values.length-i; }
8print(values);
9sort(values,0,values.length-1);
10print(values);
11}
12public static void sort(int[] numbers, int p,int r)
13{
14int q;
15if(p<r)
16{
17q = (p+r)/2;
18sort(numbers,p,q);
19sort(numbers,q+1,r);
20merge(numbers,p,q,r);
21}
22}
23/**
24* p, mid, and r are indices into the array such that p <= mid < r.
25* The procedure assumes that the subarrays 'numbers[p..mid]' and 'numbers[mid+1..r]' are
26* in sorted order. It merge them to form a single sorted subarray that replaces
27* the current subarray 'numbers[p..r]'.
28*/
29private static void merge(int[] values, int p, int mid, int r)
30{
31int i,j,k;
32int n1 = mid - p + 1;
33int n2 = r - mid;
34int[] left = new int[n1+1];
35int[] right = new int[n2+1];
36for(i=0; i<n1; i++)
37{
38left[i] = values[ p + i ];
39}
40for(j=0; j<n2; j++)
41{
42right[j] = values[mid + j + 1];
43}
44left[n1] = Integer.MAX_VALUE;
45right[n2] = Integer.MAX_VALUE;
46i=0; j=0;
47for(k=p; k<=r; k++)
48{
49if(left[i]<=right[j])
50{
51values[k] = left[i];
52i = i + 1;
53}
54else
55{
56values[k] = right[j];
57j = j + 1;
58}
59}
60}
61public static void print(int[] numbers)
62{
63int i;
64for(i=0; i<numbers.length; i++)
65{
66System.out.print(numbers[i]+ " ");
67}
68System.out.println();
69}
70}