CODEWITHSUNDEEP
javamergesort
nikhil
nikhil

Reputation: 9415

Implementing merge sort in java

Here's my implementation of Merge Sort in java

import java.io.*;
import java.util.Arrays;

public class MergeSort
{
  private static int [] LeftSubArray(int [] Array)
  {
    int [] leftHalf = Arrays.copyOfRange(Array, 0, Array.length / 2);
    return leftHalf;
  }

  private static int [] RightSubArray(int [] Array)
  {
    int [] rightHalf = Arrays.copyOfRange(Array, Array.length / 2 + 1, Array.length);
    return rightHalf;
  }

  private static int [] Sort(int [] A)
  {
    if(A.length > 1)
    {
      return Merge( Sort( LeftSubArray(A) ) , Sort( RightSubArray(A) ) );
    }
    else
    {
      return A;
    }
  }

  private static int [] Merge(int [] B, int [] C)
  {
    int [] D = new int[B.length + C.length];
    int i,j,k;
    i = j = k = 0;
    while(k < D.length)
    {
      if(i == B.length)
      {
        //Copy the remainder of C into D
        while(k < D.length){ D[k++] = C[j++]; }
      }
      if(j == C.length)
      {
        //Copy the remainder of B into D
        while(k < D.length){ D[k++] = B[i++]; }
      }
      if(i<B.length && j<C.length)
      {
        if(B[i] > C[j]){ D[k++] = B[i++]; }
        else { D[k++] = C[j++]; }
      }
    }
    return D;
  }

  public static void main(String [] args)
  {
    int [] array = {1,3,5,2,4};
    int [] sorted = MergeSort.Sort(array);
    for(int i = 0;i < sorted.length; ++i)
    {
      System.out.print(sorted[i] + " ");
    }
  }
}

The output I get is

2 1

From what I can tell there seems a problem with my division of the right sub array. What am I doing wrong?

Upvotes: 1

Views: 2060

Answers (5)

isxaker
isxaker

Reputation: 9506

I found a rigth solution in Robert Sedgewick book "Algorithms on java language"

  1. Read here about merge

Upvotes: 1

darijan
darijan

Reputation: 9795

This piece of code works: you had couple of errors: see next diffs:

  • rightSubArray method
  • copy the remainder of B
  • copy the remainder of C

The code that works follows:

public class MergeSort
{
  private static int [] LeftSubArray(int [] Array)
  {
    int [] leftHalf = Arrays.copyOfRange(Array, 0, Array.length / 2);
    return leftHalf;
  }

  private static int [] RightSubArray(int [] Array)
 {
    int[] rightHalf = Arrays.copyOfRange(Array, Array.length / 2,
            Array.length);
 return rightHalf;
 }

 private static int [] Sort(int [] A)
 {
  if(A.length > 1)
  {
    return Merge( Sort( LeftSubArray(A) ) , Sort( RightSubArray(A) ) );
  }
  else
{
  return A;
}
}

private static int [] Merge(int [] B, int [] C)
{
  int [] D = new int[B.length + C.length];
  int i,j,k;
  i = j = k = 0;
  while(k < D.length)
  {
    if(i == B.length)
    {
    //Copy the remainder of C into D
            while (j < C.length) {
                D[k++] = C[j++];
            }
  }
  if(j == C.length)
  {
    //Copy the remainder of B into D
            while (i < B.length) {
                D[k++] = B[i++];
            }
  }
        if (i < B.length && j < C.length)
  {
            if (B[i] > C[j]) {
                D[k++] = B[i++];
            } else {
                D[k++] = C[j++];
            }
  }
}
return D;
}

 public static void main(String [] args)
  {
   int [] array = {1,3,5,2,4};
   int [] sorted = MergeSort.Sort(array);
   for(int i = 0;i < sorted.length; ++i)
   {
     System.out.print(sorted[i] + " ");
   }
 }
}

Upvotes: 1

pushy
pushy

Reputation: 9645

Here is the javadoc of copyOfRange:

Parameters:
original - the array from which a range is to be copied
from - the initial index of the range to be copied, **inclusive**
to - the final index of the range to be copied, **exclusive**. (This index may lie outside the array.)

I highlighted two words you should pay special attention to ;-)

Upvotes: 3

remi dupuis
remi dupuis

Reputation: 117

With your code [1,3,5,2,4] is split into [1,3] and [2,4]. Good luck

Upvotes: 1

Scott Hunter
Scott Hunter

Reputation: 49920

If your array has 10 elements, then LeftSubArray copies elements 0..5, and RightSubArray copies elements 6..10. But if the first element is at index 0, then there is no element w/ an index 10. And if copyOfRange(a,b) gives elements indexed a..b-1, then LeftSA is yielding 0..4 and RightSA is yielding 6..9. Either way, your assumption about division seems to be accurate.

Upvotes: 2

Related Questions