Merge Sort

Merge Sort

     Merge sort เป็นการ sort ข้อมูลด้วยการแบ่งข้อมูลออกเป็นสองส่วน แล้วจึง sort ข้อมูลในแต่ละส่วน หลังจากนั้นจึงนาเอาข้อมูลทั้งสองส่วนมารวมกันตามตาแหน่งที่เหมาะสมของข้อมูลแต่ละตัว (merge) ทาการแบ่งและ merge ไปจนกว่าข้อมูลอยู่ในตาแหน่งที่ถูกต้อง

     

     ในการจัดเรียงด้วย Merge sort นั้น เราดึงเอาวิธีการของ Recursion เข้ามาใช้ดังนั้นเราจึงเห็นในรูปถึงการแบ่งข้อมูลออกเป็นสองส่วน คือส่วนที่มี 64, 21, 33, และ 70 กับส่วนที่มี 12, 85, 44 และ 3 แต่เรายัง merge ข้อมูลของทั้งสองไม่ได้เราจึงต้องแบ่งข้อมูลในส่วนแรกออกเป็นสองส่วนอีก คือส่วนที่มี 64 และ 21 กับส่วนที่มี 33 และ 70 และเนื่องจากทั้งสองส่วนแบ่งไม่ได้อีกแล้ว เราจึงทาการจัดเรียงข้อมูลในแต่ละส่วน ซึ่งทาให้เราได้ข้อมูลเป็น 21 กับ 64 และ 33 กับ 70 หลังจากนั้นเราจึง merge ข้อมูลของทั้งสองส่วนเข้าด้วยกัน เราก็ได้ 21, 33, 64 และ 70 ซึ่งเป็นข้อมูลที่มีการจัดเรียงที่เหมาะสมแล้ว

     หลังจากนั้นเราก็ทาแบบเดียวกันกับส่วนที่หนึ่ง เราจะได้ข้อมูลของส่วนหลังเป็น 3, 12, 44, 85 และเราก็ merge ข้อมูลทั้งสองส่วนเข้าด้วยกันเราจะได้ข้อมูลที่ถูกจัดเรียงเป็น 3, 12, 21, 33, 44, 64, 70, 85

ขั้นตอนการทางานของ Merge sort มีดังนี้คือ

1. ถ้าจานวนข้อมูลเป็น 0 หรือ 1 ให้ยุติการทางานนั้น (return)

2. ทาการจัดเรียงข้อมูลในส่วนทั้งสองด้วยวิธีการของ Recursion

3. รวมข้อมูลที่ได้รับการจัดเรียงในส่วนทั้งสองเข้าด้วยกัน

Algorithms Merge Sort

private static Object makeArray(Object source) {

        int length = Array.getLength(source);

        Class aClass = source.getClass();

        Class component = aClass.getComponentType();

        Object result = Array.newInstance(component, length);

        return result;

}

//Top-down merge sort

public static <T extends Comparable<? super T>>

void mergeSort(T[] arr) {

        T[] temp = (T[])makeArray(arr); //compiler warning!

         mergeSort(arr, 0, arr.length-1, temp);

}

//recursive merging routines

private static <T extends Comparable<? super T>>

void mergeSort(T[] arr, int left, int right, T[] temp) {

        //exit recursive call

        if(right <= left)

             return;

        int mid = (left + right) / 2; //divide into halves

        mergeSort(arr, left, mid, temp); //merge first half

        mergeSort(arr, mid+1, right, temp); //merge second half

        merge(arr, left, mid, right, temp); //merging two sorted halves

}

//merging two sorted lists

private static <T extends Comparable<? super T>>

void merge(T[] arr, int left, int mid, int right, T[] temp) {

       int i, j;

       //move first array

       for(i = mid+1; i > left; i--)

            temp[i-1] = arr[i-1];

//move second array

       for(j = mid; j < right; j++)

             temp[right+mid-j] = arr[j+1];

//merge those two arrays

        for(int k = left; k <= right; k++)

             if(temp[j].compareTo(temp[i]) < 0)

                  arr[k] = temp[j--];

             else

                  arr[k] = temp[i++];

}