Blog Merge Sort

Merge Sort 

Ide algoritma ini hampir mirip dengan QuickSort, yaitu melakukan partisi.

Kecuali bahwa algoritma ini melakukan partisi tanpa kriteria.

Jadi, data set (X[l] ... X[r]) di partisi langsung ke du sub data set dengan jumlah data yang

sama (X[l] ... X[(l+r)/2], dan X[(l+r)/2+1] ... X[r]).

Lalu secara rekursif melakukan Merge Sort untuk masing-masing data set.

Karena kedua data set itu bisa overlapping (tidak seperti pada Quick Sort) maka setelah

kedua sub data set terurut masih memerlukan proses penggabungan (Merging).

Merging ini memerlukan ruang tambahan yaitu suatu array yang sama panjangnya dengan

panjang kedua subset untuk menyimpan hasilnya.

void MergeSort(int l,int r) {

if (l < r) {

MergeSort(l, (l+r)/2);
MergeSort((l+r)/2,r);
Merging();

}

}

Algoritma ini memiliki kompleksitas O(n log n).

 Implementasinya Seperti Ini :

package Praktikum_4;

/**

 *

 * @author Angga

 */

/**

 * The MergeSort class uses the merge

 * sort algorithm to sort an array of integers

 * into non-decreasing order.

 */

public class MergeSort{

 

  public static void mergeSort_srt(int array[],int lo, int n){

    int low = lo;

    int high = n;

    if (low >= high) {

      return;

    }

    int middle = (low + high) / 2;

    mergeSort_srt(array, low, middle);

        mergeSort_srt(array, middle + 1, high);

    int end_low = middle;

    int start_high = middle + 1;

    while ((lo <= end_low) && (start_high <= high)) {

      if (array[low] < array[start_high]) {

        low++;

            } else {

        int Temp = array[start_high];

        for (int k = start_high- 1; k >= low; k--) {

          array[k+1] = array[k];

        }

                array[low] = Temp;

                low++;

                end_low++;

                start_high++;

            }

        }

    }

  public static void main(String a[]){

    int i;

    int array[] = {4,6,7,8,12,34,5,6,78};

   // System.out.println("\n\n       RoseIndia\n\n");

    //System.out.println("       Selection Sort\n\n");

    //System.out.println("Values Before the sort:\n");

    for(i = 0; i < array.length; i++)

      System.out.print( array[i]+"  ");

    System.out.println();

    mergeSort_srt(array,0, array.length-1);

    //System.out.print("Values after the sort:\n");

    for(i = 0; i

      System.out.print(array[i]+"  ");

    System.out.println();

    System.out.println("Stop");

  }

}