Jawaban:

Berikut adalah algoritma Merge Sort:

1. Jika array hanya memiliki satu elemen atau tidak ada elemen, kembalikan array tersebut

2. Hitung titik tengah dari array

3. Rekursif panggil Merge Sort pada setengah kiri array (mulai dari indeks 0 hingga tengah)

4. Rekursif panggil Merge Sort pada setengah kanan array (mulai dari tengah hingga akhir)

5. Gabungkan setengah kiri dan kanan array dengan urutan yang sesuai (panggil method merge)

6. Kembalikan array yang telah diurutkan

Method merge (array1, array2):

1. Buat array baru untuk menampung hasil penggabungan

2. Inisialisasi variabel penunjuk indeks untuk array1 dan array2

3. Looping hingga kedua array telah diambil semua elemennya:

  a. Jika array1 lebih kecil dari array2, masukkan elemen array1 ke array baru dan tambahkan indeks array1 dengan 1

  b. Jika array2 lebih kecil atau sama dengan array1, masukkan elemen array2 ke array baru dan tambahkan indeks array2 dengan 1

4. Masukkan elemen yang tersisa pada array1 ke array baru

5. Masukkan elemen yang tersisa pada array2 ke array baru

6. Kembalikan array baru yang telah dihasilkan

Berikut adalah program Java untuk algoritma Merge Sort menggunakan method main():

import java.util.Arrays;

public class MergeSort {

   public static void mergeSort(int[] arr) {

       if (arr.length > 1) {

           int mid = arr.length / 2;

           int[] leftArr = Arrays.copyOfRange(arr, 0, mid);

           int[] rightArr = Arrays.copyOfRange(arr, mid, arr.length);

           mergeSort(leftArr);

           mergeSort(rightArr);

           int i = 0;

           int j = 0;

           int k = 0;

           while (i < leftArr.length && j < rightArr.length) {

               if (leftArr[i] < rightArr[j]) {

                   arr[k] = leftArr[i];

                   i++;

               } else {

                   arr[k] = rightArr[j];

                   j++;

               }

               k++;

           }

           while (i < leftArr.length) {

               arr[k] = leftArr[i];

               i++;

               k++;

           }

           while (j < rightArr.length) {

               arr[k] = rightArr[j];

               j++;

               k++;

           }

       }

   }

   public static void main(String[] args) {

       int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};

       System.out.println("Before sorting: " + Arrays.toString(arr));

       mergeSort(arr);

       System.out.println("After sorting: " + Arrays.toString(arr));

   }

}

Program ini mengandung 1 method utama, yaitu:

mergeSort: method untuk melakukan Merge Sort. Method ini mengambil sebuah array integer sebagai parameter dan mengurutkan elemen-elemennya menggunakan algoritma Merge Sort.