Merge Sort : Bugs in this code

I get index out of bounds exception when i try to run this code .

we are using two different array s left and right for merging ..

and using recursive merge sort to divide the array into individaul elements and merging them...

Here's the algorithm from CLRS i am using :

    Merge(A, p, q, r)
    n1 ← q - p + 1
    n2 ← r - q
    create arrays L[1..n1 + 1] and R[1..n2 + 1]
    for i ← 1 to n1
    do L[i] ← A[p + i - 1]
    for j ← 1 to n2
      do R[j] ← A[q + j]
    L[n1 + 1] ← ∞
    L[n2 + 1] ← ∞
    i ← 1
    j ← 1
    for k ≤ p to r
        do if L[i] ≤ R[j]
          then A[k] ← L[i]
             i ← i + 1
          else A[k] ← R[j]
   开发者_开发知识库           j ← j + 1

     MergeSort(A, p, r)
     if p < r
      then q ← ⌊(p + r)/2⌋
       MergeSort(A, p, q)
       MergeSort(A, q + 1, r)
       Merge(A, p, q, r)

here's the code:

import java.util.Arrays;
import java.util.Scanner;

public class MergeSort {
   public static void main(String[] args) {
      Scanner input = new Scanner(System.in);
      System.out.println("Enter the size of array to be sorted");
      int size = input.nextInt();
      int[] A = new int[size];
      System.out.println("Enter the elements of array");
      for (int i = 0; i < A.length; i++) {
         A[i] = input.nextInt();
      }
      System.out.println("The UNSORTED array elements are" + Arrays.toString(A));
      int p = 0, r = size;
      mergeSort(A, p, r);
      System.out.println("The SORTED array elements are" + Arrays.toString(A));
   }

   public static void mergeSort(int[] A, int p, int r) {
      if (p < r) {
         int q = (p + r) / 2;
         mergeSort(A, p, q);
         mergeSort(A, q + 1, r);
         merge(A, p, q, r);
      }
   }

   public static void merge(int[] A, int p, int q, int r) {
      int n1 = q - p + 1;
      int n2 = r - q;
      int[] L = new int[n1 + 1];
      int[] R = new int[n2 + 1];
      L[n1] = Integer.MAX_VALUE;
      R[n2] = Integer.MAX_VALUE;
      for (int i = 0; i < n1; i++) {
         L[i] = A[p + i];
      }
      for (int j = 0; j < n2; j++) {
         R[j] = A[q + j + 1];
      }
      int x = 0, y = 0;
      for (int k = p; k < r; k++) {
         if (L[x] <= R[y]) {
            A[k] = L[x];
            x++;
         } else {
            A[k] = R[y];
            y++;
         }
      }
   }
}

---

After a second but longer look, your implementation of the algorithm seems to be right, i got confused regarding your input parameters because they did not fit your zero based implementation. So maybe you do not want to call it like this:

int p = 0, r = size;
mergeSort(A, p, r);

but rather like this:

int p = 0, r = size - 1;
mergeSort(A, p, r);

---

Just for the sake of completeness, and after the change that Gandalf suggested, in the merge() method the for loop should include the value of r, so by replacing

for (int k = p; k < r; k++) {

with

for (int k = p; k <= r; k++) {

your implementation sorts the array correctly.