CoE KKU

Mergesort มี running time เป็น $O(N\ log\ N)$ กรณี worst-case และใช้จำนวนครั้งในการเทียบค่าที่เกือบจะ optimal และเป็นตัวอย่างที่ดีของอัลกอริทึมแบบ recursive

การทำงานพื้นฐานในอัลกอริทึมคือ การควบรวมรายการที่มีการจัดเรียงไว้แล้ว 2 รายการเข้าด้วยกัน เนื่องจากรายการที่จะนำมาควบรวมนั้นเป็นรายการที่มีการจัดเรียงไว้แล้ว ดังนั้นจึงสามารถทำได้ด้วยการอ่านอินพุตเข้าเพียงรอบเดียว และนำผลไปไว้ในรายการที่สามที่แยกออกไปต่างหาก

อัลกอริทึมพื้นฐานของการควบรวมคือจะใช้อะเรย์ที่เป็นอินพุตสองชุดคือ อะเรย์ a และ b, และ อะเรย์สำหรับเอาต์พุตคืออะเรย์ c, และตัวนับ (counter) สามตัว คือ aptr, bptr, และ cptr ซึ่งตั้งค่าให้อยู่ที่จุดเริ่มต้นของอะเรย์แต่ละตัวตามลำดับ ทำการคัดลอกค่าที่น้อยกว่าระหว่างค่าของ a[aptr] และ b[bptr] ไปใส่ลงในช่องว่างถัดไปของ c แล้วเพิ่มค่าของตัวนับตัวที่ถูกคัดลอก และ ตัวนับของ c เมื่อสิ้นสุดอะเรย์ตัวใดตัวหนึ่งก็ให้ทำการคัดลอกสมาชิกที่เหลือของอีกอะเรย์หนึ่งไปไว้ใน c ตามลำดับที่ปรากฏนั้น ๆ รูปต่อไปนี้เป็นตัวอย่างของการควบรวมอินพุตสองชุด

ถ้าอะเรย์ a บรรจุค่า 1, 13, 24, 26 และ b บรรจุค่า 2, 15, 27, 38 การทำงานของอัลกอริทึมก็จะเป็นดังนี้ เริ่มต้นด้วยการเทียบค่าระหว่าง 1 และ 2 ดังนั้น บรรจุค่า 2 ลงใน c จากนั้นเทียบค่าระหว่าง 13 และ 2

เพิ่ม 2 ลงใน c แล้วเปรียบเทียบค่า 13 และ 15

เพิ่ม 13 ลงใน c แล้วเปรียบเทียบค่า 24 และ 15 ทำต่อไปเรื่อย ๆ จนกระทั่งถึงการเทียบค่าระหว่าง 26 และ 27

เพิ่ม 26 ลงใน c ก็จะหมดสมาชิกใน a

คัดลอกสมาชิกทั้งหมดที่เหลือใน b ไปไว้ใน c

เวลาที่ใช้ในการควบรวมรายการสองรายการที่จัดเรียงไว้แล้วเป็นแบบ linear เนื่องจากต้องใช้การเปรียบเทียบค่าอย่างมากที่สุด N - 1 ครั้งเมื่อ N คือจำนวนสมาชิกทั้งหมด กล่าวคือทุก ๆ การเทียบค่าแต่ละครั้งจะเป็นการเพิ่มสมาชิกลงใน c หนึ่งตัว ยกเว้นการเทียบค่าครั้งสุดท้ายที่ต้องเพิ่มค่าใน c สองตัว

อัลกอริทึมของ mergesort อธิบายได้ดังนี้

ถ้าจำนวนสมาชิกที่ต้องจัดเรียง N = 1 คือมีสมาชิกตัวเดียวก็จะได้คำตอบในทันที

แต่ถ้า N > 1 ก็จะทำ mergesort แบบ recursive โดยทำกับครึ่งแรกก่อนแล้วจึงทำกับครึ่งหลัง

การทำเช่นนี้จะได้รายการที่มีการจัดเรียงครึ่งหนึ่ง 2 ชุดซึ่งสามารถนำมาควบรวมกันด้วยอัลกอริทึมสำหรับการควบรวมที่กล่าวมาแล้วข้างบน

เช่น ต้องการจัดเรียงอะเรย์ขนาดสมาชิก 8 ตัว คือ 24, 13, 26, 1, 2, 27, 38, 15

เราจะทำการจัดเรียง 4 ตัวแรกและ 4 ตัวหลังในแบบ recursive ซึ่งจะได้อะเรย์เป็น 1, 13, 24, 26, 2, 15, 27, 38, จากนั้นก็จะทำการควบรวมทั้งสองครึ่งดังกล่าวเข้าด้วยกัน จะได้รายการสุดท้ายคือ 1, 2, 13, 15, 24, 26, 27, 38,

อัลกอริทึมดังกล่าวนี้รู้จักกันในชื่อของ divide-and-conquer กล่าวคือ จะแบ่งปัญหา (divide) ออกเป็นปัญหาย่อยแล้วแก้ปัญหาย่อยนั้นแบบ recursive ในขั้นของ conquer คือการรวมคำตอบของปัญหาย่อยเข้าด้วยกัน อัลกอริทึม Divide-and-conquer เป็นอัลกอริทึมที่มีประสิทธิภาพมากเมื่อใช้วิธีแบบ recursive

รูปที่ 7.9 แสดงฟังก์ชัน mergesort ฟังก์ชัน mergeSort ที่เป็น public เป็นตัว driver เรียกใช้ฟังก์ชัน mergeSort ที่เป็น แบบ private รูปที่ 7.10 แสดงฟังก์ชัน merge

public static void mergeSort( Comparable [ ] a )
{   Comparable [ ] tmpArray = new Comparable[ a.length ];
    mergeSort( a, tmpArray, 0, a.length - 1 );
}
 
private static void mergeSort( Comparable [ ] a, Comparable [ ] tmpArray, int left, int right )
{   if( left < right )
    {   int center = ( left + right ) / 2;
        mergeSort( a, tmpArray, left, center );
        mergeSort( a, tmpArray, center + 1, right );
        merge( a, tmpArray, left, center + 1, right );
    }
} 

รูปที่ 7.9 ฟังก์ชัน mergesort

private static void merge( Comparable [ ] a, Comparable [ ] tmpArray, int leftPos, int rightPos, int rightEnd )
{
    int leftEnd = rightPos - 1;
    int tmpPos = leftPos;
    int numElements = rightEnd - leftPos + 1;
    while( leftPos <= leftEnd && rightPos <= rightEnd ) // Main loop
        if( a[ leftPos ].compareTo( a[ rightPos ] ) <= 0 )
            tmpArray[ tmpPos++ ] = a[ leftPos++ ];
        else
            tmpArray[ tmpPos++ ] = a[ rightPos++ ];
    while( leftPos <= leftEnd )    	// Copy rest of first half
        tmpArray[ tmpPos++ ] = a[ leftPos++ ];
    while( rightPos <= rightEnd )  	// Copy rest of right half
        tmpArray[ tmpPos++ ] = a[ rightPos++ ];
    for( int i = 0; i < numElements; i++, rightEnd-- )// Copy tmpArray back
        a[ rightEnd ] = tmpArray[ rightEnd ];
  }

รูปที่ 7.10 ฟังก์ชัน merge

เราต้องหา recurrence relation ของ running time สมมุติให้ N เป็นเลขยกกำลังของ 2 กล่าวคือ ให้ N = 2k เมื่อ k เป็นเลขจำนวนเต็มทั้งนี้ก็เพื่อว่าเราจะสามารถแบ่งจำนวนข้อมูลออกเป็นสองส่วนส่วนละครึ่งได้เสมอ สำหรับ N = 1 เวลาที่ใช้ใน mergesort เป็นค่าคงที่ ซึ่งจะให้มีค่าเป็น 1 กรณีถ้า N > 1 เวลาที่ใช้ใน mergesort สำหรับ N จำนวนจะเท่ากับเวลาที่ใช้ในการทำ mergesorts แบบ recursive จำนวนสองครั้งกับข้อมูลขนาด N/2 บวกกับเวลาที่ใช้ในการควบรวมซึ่งเป็น linear ดังนั้น จะได้สมการดังนี้ $$ T(1) = 1$$ $$ T(N) = 2T(N/2) + N $$ เมื่อแก้สมการ recurrence ข้างบนจะได้ $T(N) = O(N\ lg\ N)$