martes, 15 de junio de 2010

Sorting - Merge Sort


public static int[] mergeSort( int[] a)
{
   if (a.length > 1)
   {
      int middle = (a.length/2);
      int[] b = Arrays.copyOfRange(a, 0, middle);// copy a[0...middle-1] to b
      int[] c = Arrays.copyOfRange(a, middle, a.length);//copy a[middle... a.length -1] to c

      b = mergeSort(b);
      c = mergeSort(c);
      a = merge(b,c);
   }
   return a;
}

private static int[] merge(int[] b, int[] c)
{

   int[] merged = new int[b.length + c.length ];
   int i =0, j =0, k =0;
   while (i < b.length && j < c.length)
   {
      if (b[i] <= c[j])
      {
         merged[k]= b[i];
         i++;
      }
      else
      {
         merged[k]= c[j];
         j++;
      }
      k++;
   }
   if (i == b.length)
      System.arraycopy(c, j, merged, k, c.length-j);
   else
      System.arraycopy(b, i, merged, k,b.length-i);
   return merged;
}

//Testing

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

public static void main(String args[])
{
   int a[]={0,5,3,1,9,8,22,4,7,6,45};
   showArray(a);
   a=mergeSort(a);
   showArray(a);
}

No hay comentarios:

Publicar un comentario