ข้อมูลที่เรียงลำดับแล้ว เราสามารถเรียกใช้ หรือค้นหาได้เร็วขึ้น เช่นแฟ้มระเบียน น.ศ. เรียงตามลำดับรหัส สมุดโทรศัพท์หรือพจนานุกรม เรียงตามลำดับตัวอักษรเป็นต้น

ในการเรียงข้อมูล เราต้องกำหนดคีย์ เช่นถ้าคีย์ i < j หมายความว่าข้อมูลลำดับที่ i ต้องมาก่อนข้อมูลลำดับที่ j โดยปกติแล้ว คีย์จะเป็นตัวอักษรหรือตัวเลข เช่น ข้อมูล น.ศ. ทีประกอบด้วยชื่อ รหัส สาขา เกรดเฉลี่ย เราอาจะเรียงข้อมูลตามลำดับชื่อหรือรหัส ก็ได้ )

ในที่นี้จะยกตัวอย่างการเรียงข้อมูล 4 วิธีคือ Bubble sort, Insert sort, Merge sort และ Quick sort ซึ่งมีค่า Big O เป็น N2, N2, N log N และ N log N ตามลำดับ

วิธีการคือ ให้ตรวจสอบข้อมูลทั้งหมด หลายๆรอบ แต่ละรอบจะมีการเปรียบเทียบข้อมูลที่อยู่ติดกัน แล้วสลับเพื่อให้เรียงตามลำดับ ในแต่ละรอบ ข้อมูลตัวที่มากที่สุด (หรือน้อยที่สุด) จะมาอยู่ในลำดับที่ถูกต้อง รอบต่อไปก็ให้เรียงเฉพาะข้อมูลที่เหลือ (ไม่รวมตัวที่เรียงแล้ว) จำนวนรอบทั้งหมดคือ N-1 รอบ เมื่อ N คือจำนวนข้อมูลทั้งหมด อย่างไรก็ตามข้อมูลอาจเรียงเรียบร้อย ก่อนที่จะครบ N-1 รอบ

วิธีการคือการแทรกข้อมูลแต่ละตัวในตำแหน่งที่เรียงตามลำดับ จำนวนรอบในการแทรกคือ N-1 รอบ โดยที่ N คือจำนวนของข้อมูล ในแต่ละรอบ จะมีการแทรกและสลับข้อมูล ทำให้ข้อมูลตั้งแต่รอบแรกถึงรอบปัจจุบัน อยู่ในลำดับที่ถูกต้อง บางรอบ (ถ้าโชคดี) ก็จะไม่มีการสลับกันของข้อมูลเลย วิธีการนี้เหมาะกับการเรียงข้อมูลที่มีจำนวนน้อย หรือใกล้จะเรียงแล้ว

• เรียงข้อมูล N-1 รอบ แต่ละรอบเปรียบเทียบข้อมูล N-1 ครั้ง
• จำนวนครั้งในการทำงานคือ (N-1)*(N-1) = N2 – 2N + 1 จะได้ Big O เป็น O(N2)
• แต่ในกรณีที่ข้อมูลมีจำนวนน้อยหรือข้อมูลส่วนใหญ่เกือบเรียงแล้ว Insertion sort O(N2)จะทำงานได้เร็วกว่า O(N log N) ดังนั้นอัลกอริทึมใหม่ๆ จึงใช้งาน Insertion sort ร่วมกับ merge sort หรือ quick sort เมื่อจำนวนข้อมูลจากการแบ่งครึ่งมีจำนวนน้อย

เป็นการเรียงข้อมูลที่เร็วที่สุด ดีที่สุด (จึงได้ชื่อว่า quick sort)

หลักการคือ divide-and-conquer แบ่งแยกแล้วรวม โดยทำการแบ่งข้อมูลทั้งหมดออกเป็น 2 กลุ่ม โดยกลุ่มแรกจะเป็นกลุ่มของข้อมูลที่มีค่าน้อยกว่าค่ากลางที่กำหนด และส่วนที่สองเป็นกลุ่มของข้อมูลที่มีค่ามากกว่าค่ากลางที่กำหนด หลังจากนั้นแบ่งข้อมูลแต่ละส่วนออกเป็น 2 ส่วนเช่นเดิม แบ่งไปเรื่อยๆจนเหลือตัวเดียว ซึ่งเป็นข้อมูลที่เรียงแล้วนั่นเอง

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

Quick sort เหมาะสำหรับข้อมูลที่มีจำนวนมากและกระจายแบบสุ่ม ไม่เป็นระเบียบ ไม่ควรใช้ quick sort กับจำนวนข้อมุลเพียงเล็กน้อยและเกือบๆจะเรียงแล้ว

1. ให้เลือก pivot โดยเลือกตัวกลางระหว่างสามตัว (median of three) แล้วสลับกันกับข้อมูลตัวสุดท้าย
2. กำหนดตัวชี้ 2 ตัว up และ down โดยที่ down ชี้ไปที่ข้อมูลตัวแรก และ up ชี้ไปที่ข้อมูลตัวสุดท้ายก่อนหน้า 3. ให้เลื่อน down ไปทางขวาเรื่อยๆจนกว่าจะได้ข้อมูลที่มีค่ามากกว่า pivot
4. ให้เลื่อ up ไปทางซ้ายเรื่อยๆจนกว่าจะได้ข้อมูลที่มีค่าน้อยกว่า pivot
5. ถ้า up > down ให้สลับข้อมูลในตำแหน่ง down และ up
6. ให้ทำซ้ำข้อ 3 และ 4 จนกระทั่ง up <= down ก็ให้สลับข้อมูลในตำแหน่ง down กับ pivot
7. เราจะได้ข้อมูลแบ่งออกเป็นสองส่วนโดยมี pivot อยู่ตรงกลางในตำแหน่งที่เรียงแล้ว หลังจากนั้น ก็ให้ทำการเรียงข้อมูลในส่วนแรก และส่วนที่สองต่อไป โดยทำซ้ำข้อ 1 ถึง 7 จนกว่าจะเหลือข้อมูลในแต่ละส่วนเพียงตัวเดียว

เป็นการนำค่าของอาร์เรย์ตัวแรก a[0] ตัวตรงกลาง a[(N-1)/2] และตัวสุดท้าย a[N-1] มาเรียงตามลำดับจากน้อยไปมาก และเลือกตัวตรงกลางเป็น pivot

   // Internal quicksort method that makes recursive calls.
	// Uses median-of-three partitioning and a cutoff of 10.
	// a is an array of AnyType items.
	// low is the left-most index of the subarray.
	// high is the right-most index of the subarray.
	private static void Quicksort(AnyType[] a, int low, int high) where AnyType : IComparable
        {
            if (low + CUTOFF > high)
                InsertionSort(a, low, high);
            Else {
                // Sort low, middle, high
                int middle = (low + high) / 2;
                if (a[middle].CompareTo(a[low]) < 0)
                    Swap(ref a[low], ref a[middle]);
                if (a[high].CompareTo(a[low]) <  0)
                    Swap(ref a[low], ref a[high]);
                if (a[high].CompareTo(a[middle]) <0)
                    Swap(ref a[middle], ref a[high]);

                // Place pivot at position high - 1
                Swap(ref a[middle], ref a[high - 1]);
                AnyType pivot = a[high - 1];
                // Begin partitioning
                int i, j;
                for (i = low, j = high - 1; ;)
                {
                    while (a[++i].CompareTo(pivot) < 0)
                        ;
                    while (pivot.CompareTo(a[--j]) < 0)
                        ;
                    if (i >= j)
                        break;
                    Swap(ref a[i], ref a[j]);
                }
                // Restore pivot
                Swap(ref a[i], ref a[high - 1]);

                Quicksort(a, low, i - 1);    // Sort small elements
                Quicksort(a, i + 1, high);   // Sort large elements
            }
}

   

• จำนวนครั้งในการแบ่งครึ่งจนเหลือข้อมูลตัวเดียวคือ log N
• จำนวนครั้งในการเรียงในแต่ละครึ่งคือ N
• จะได้ Big O เป็น O(N log N)
• แต่ในกรณีที่ข้อมูลส่วนใหญ่เกือบเรียงแล้ว เราจะไม่ได้ pivot อยู่ตรงกลาง แต่จะอยู่ชิดขอบด้านใดด้านหนึ่ง ทำให้จำนวนครั้งในการแบ่งเป็น N ซึ่งจะได้ Big O เป็น O(N2) ดังนั้น quick sort จึงไม่เหมาะกับจำนวนข้อมูลน้อยๆ และเกือบจะเรียงแล้ว

เป็นวิธีการเรียงข้อมูลแบบ แบ่งแยกแล้วรวม คล้ายกับ quck sort โดยทำการแบ่งข้อมูลที่ละครึ่งไปเรื่อยๆ จนเหลือเพียงตัวเดียว หลังจากนั้นก็ทำการรวมเข้าด้วยกัน จาก 1 เป็น 2 เป็น 4 เป็น 8 จนครบจำนวนข้อมูลทั้งหมด

ในขณะที่รวมก็จะมีการเรียงไปด้วยดังนี้ โดยใช้อาร์เรย์สำหรับเก็บข้อมูลชั่วคราวเพิ่มอีก 1 ชุด วิธีการนี้เรียกว่า divide and conquer แบ่งแยกแล้วรวม คือแบ่งอาร์เรย์ N เป็นอาร์เรย์ย่อยๆที่มีแค่ตัวเดียว จากนั้นก็รวมแต่ละคู่ของอาร์เรย์ที่อยู่ติดกันเรื่อยๆ จนได้อาร์เรย์ขนาด N เท่าเดิม

1. กำหนดอาร์เรย์ที่ถูกแบ่งครึ่งแล้วคือ A และ B ส่วน C เป็นอาร์เรย์ที่ได้จากการรวม A และ B และกำหนดตัวชี้ Ac,Bc, Cc ให้ชี้ไปที่ตำแหน่งต่างๆของอาร์เรย์ A, B และ C ตามลำดับ
2. ค่าที่น้อยกว่าของอาร์เรย์ A[Ac] และ B[Bc] ให้คัดลอกไปใส่ในอาร์เรย์ C และเพิ่มตัวชี้ของแต่ละอาร์เรย์เมื่อคัดลอกแล้ว
3. เมื่ออาร์เรย์ A หรือ B คัดลอกไปหมดแล้ว ให้คัดลอกส่วนที่เหลือทั้งหมดไปยังอาร์เรย์ C

• จำนวนครั้งในการแบ่งครึ่งจนเหลือข้อมูลตัวเดียวคือ log N
• จำนวนครั้งในการเรียงในแต่ละครึ่งคือ N
• จะได้ Big O เป็น O(N log N) เสมอ โดยเฉลี่ยจะเร็วกว่า quick sort เพราะเป็นการแบ่งทีละครึ่งในทุกๆรอบการแบ่ง แต่ข้อเสียของ merge sort คือต้องใช้พื้นที่ในการเรียงข้อมูลเป็นสองเท่าของ quick sort