Algoritma sorting Merge Sort

Secara   konseptual,  untuk  sebuah array  berukuran  n,
Merge Sort bekerja sebagai berikut:
1.  Jika  bernilai  0   atau   1,   maka  array  sudah   terurut.
2.   Jika Array tidak terurut, bagi menjadi 2 sub-array dengan ukuran n/2
3. Urutkan setiap sub array. Jika sub array tidak cukup kecil lakukan langkah kedua dengan rekursif
4. Menggabungkan sub array menjadi satu array

Ilustrasi Dalam Gambar

implementasi merge sort menggunakan java

 /*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package merge_sort;

import java.util.Arrays;
import javax.swing.JFrame;
import javax.swing.JOptionPane;

/**
 *
 * @author Nur_Hidayat
 */
public class Mergesort {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
     try{
            int jmldata=Integer.parseInt(JOptionPane.showInputDialog("Masukkan Jumlah Data "));
        int []arr=new int[jmldata];
        String ctk=" ";
        for (int i=0;i<jmldata;i++){//melakukan perulangan untuk memunculkan input dialog sesuai jumlah data
            arr[i]=Integer.parseInt(JOptionPane.showInputDialog("Masukkan Data Ke"+(i+1)));
            ctk=ctk+arr[i]+" ";
        }
        JFrame frame=new JFrame();
        JOptionPane.showMessageDialog(frame,"Sebelum Di Urutkan: " + ctk);
        mergeSort(arr);
        JOptionPane.showMessageDialog(frame,"Setelah Di Urutkan: " + Arrays.toString(arr));
        System.exit(0);
        }catch (NumberFormatException ee) {
            JOptionPane.showMessageDialog(null,"Mohon Masukkan Angka");
        }catch (Exception e) {
        JOptionPane.showMessageDialog(null,e);    // TODO code application logic here
    }
}
    public static void mergeSort(int[] array) {
        if (array.length > 1) {
            //membagi array menjadi dua bagian
            int[] left = leftHalf(array);
            int[] right = rightHalf(array);
           
            /** melakukan pemanggilan metod oleh dirinya sendiri (rekursif)
            * untuk membagi array menjadi bagian yang lebih kecil sampai
            * elemen paling kecil
            */
            mergeSort(left);
            mergeSort(right);
           
            // menggabungkan bagian diurutkan menjadi suatu kesatuan yang diurutkan
            merge(array, left, right);
        }
    }
   
    // Mengembalikan bagian pertama dari array yang diberikan.
    public static int[] leftHalf(int[] array) {
        int size1 = array.length / 2;
        int[] left = new int[size1];
        for (int i = 0; i < size1; i++) {
            left[i] = array[i];
        }
        return left;
    }
   
    // Mengembalikan bagian kedua dari array yang diberikan.
    public static int[] rightHalf(int[] array) {
        int size1 = array.length / 2;
        int size2 = array.length - size1;
        int[] right = new int[size2];
        for (int i = 0; i < size2; i++) {
            right[i] = array[i + size1];
        }
        return right;
    }
   
    // membuat array result untuk menampung hasil pengurutan dari array kiri dan kanan
    //jika result kosong maka kanan atau kiri di urutkan
    //result berisi hasil pengurutan array kiri dan kanan
    public static void merge(int[] result,
                             int[] left, int[] right) {
        int i1 = 0;   // index kedalam aray kiri
        int i2 = 0;   // index kedalam aray kanan
       
        for (int i = 0; i < result.length; i++) {
            if (i2 >= right.length || (i1 < left.length &&
                    left[i1] <= right[i2])) {
                result[i] = left[i1];    // ambil dari kiri
                i1++;
            } else {
                result[i] = right[i2];   // ambil dari kanan
                i2++;
            }
        }
    }
}


Untuk mengunduh program bisa anda download Disini