DSA_problems_OOPs/Merge Sort.java at 01.-Beginning · Abbay1235/DSA_problems_OOPs · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
import java.io.*;
import java.util.*;

public class Main {
//   public static void mergeSort(int[] arr, int left, int right) {
//     // base case
//     if(left == right)
//     { return; }

//     int mid = (left + right) / 2;

//     // Faith
//     mergeSort(arr, left, mid);
//     mergeSort(arr, mid + 1, right);

//     // Meeting Faith with Expectation
//     int[] mergedArray = mergeTwoSortedArrays(arr, left, mid, mid + 1, right);
//     for(int i=left; i<=right; i++)
//         arr[i] = mergedArray[i - left];
//   }
 //   public static int[] mergeTwoSortedArrays(int[] a, int p1, int p2, int p3, int p4) {
//     int i = p1, j = p3, k = 0;
//     int[] ans = new int[(p2 - p1 + 1) + (p4 - p3 + 1)];
//     while(i <= p2 && j <= p4){
//         if(a[i] <= a[j]){
//           ans[k] = a[i];
//           i++;
//           k++;
//         }else{
//           ans[k] = a[j];
//           j++;
//           k++;
//         }
//     }

//     while(i <= p2){
//       ans[k] = a[i];
//       k++;
//       i++;
//     }

//     while(j <= p4){
//       ans[k] = a[j];
//       k++;
//       j++;
//     }

//     return ans;
//   }

  public static int[] mergeSort(int[] arr, int left, int right) {
    // base case
    if(left == right)
    {
        int[] res = new int[1];
        res[0] = arr[left];
        return res;
    }

    int mid = (left + right) / 2;

    // Faith
    int[] leftSortedArray = mergeSort(arr, left, mid);
    int[] rightSortedArray = mergeSort(arr, mid + 1, right);

    // Meeting Faith with Expectation
    int[] mergedArray = mergeTwoSortedArrays(leftSortedArray, rightSortedArray);
    return mergedArray;
  }
  //used for merging two sorted arrays
  public static int[] mergeTwoSortedArrays(int[] a, int[] b){
    System.out.println("Merging these two arrays ");
    System.out.print("left array -> ");
    print(a);
    System.out.print("right array -> ");
    print(b);
    int i = 0, j =0, k = 0;
    int[] ans = new int[a.length + b.length];
    while(i < a.length && j < b.length){
        if(a[i] <= b[j]){
          ans[k] = a[i];
          i++;
          k++;
        }else{
          ans[k] = b[j];
          j++;
          k++;
        }
    }

    while(i < a.length){
      ans[k] = a[i];
      k++;
      i++;
    }

    while(j < b.length){
      ans[k] = b[j];
      k++;
      j++;
    }

    return ans;
  }

  public static void print(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }

  public static void main(String[] args) throws Exception {
    Scanner scn = new Scanner(System.in);
    int n = scn.nextInt();
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
      arr[i] = scn.nextInt();
    }
    int[] sa = mergeSort(arr,0,arr.length - 1);
    System.out.print("Sorted Array -> ");
    // mergeSort(arr, 0, arr.length - 1);
    // print(arr);
    print(sa);
  }

}