อธิบาย Merge Sort ใน Python

Merge sort เป็นเทคนิคการเรียงลำดับ เป็นอัลกอริธึมการเรียงลำดับที่มีประสิทธิภาพโดยมีเวลาซับซ้อนของ (n logn ) โดยที่ n คือความยาวของอาร์เรย์ที่จะจัดเรียง

Merge sort เป็นอัลกอริธึมที่เป็นไปตามกระบวนทัศน์ Divide and Conquers มันแบ่งอาร์เรย์ออกเป็นสองส่วนเท่า ๆ กันอย่างต่อเนื่อง หลังจากนั้นจะเริ่มเรียงลำดับรายการที่มีองค์ประกอบเดียวและรวมรายการที่เรียงลำดับอย่างต่อเนื่องเพื่อสร้างรายการที่เรียงลำดับทั้งหมด

ดังนั้นเราจึงได้รับอาร์เรย์ที่จัดเรียง

ตัวอย่าง

กล่องสีม่วงและลูกศรสีดำแสดงการแยกรายการออกเป็นสองส่วน

กล่องสีเขียวและลูกศรสีแดงแสดงการรวมกันของสองรายการที่เรียงลำดับแล้ว

ใช้การเรียงลำดับการผสาน

การแบ่งรายการออกเป็นสองส่วนนั้นค่อนข้างง่ายและจะทำแบบเรียกซ้ำจนกว่าเราจะเหลือองค์ประกอบเดียว ภายหลังขั้นตอนการผสานเสร็จสิ้น ซึ่งเป็นที่ที่เราใช้ตรรกะของการรวมรายการที่เรียงลำดับทั้งสองเข้าด้วยกัน

ตัวอย่าง

ฟังก์ชันผสานจะนำอาร์เรย์ที่เรียงลำดับสองชุดมารวมกัน องค์ประกอบด้านหน้าสุดของ a1 เปรียบเทียบกับองค์ประกอบที่อยู่ด้านหน้าสุดของ a2 ตัวที่เล็กที่สุดของสองตัวจะถูกเพิ่มลงในรายการ c และตัวชี้ของอาร์เรย์นั้นจะเพิ่มขึ้น

def merge(a1,a2):
   c=[]
   x=0
   y=0
   while(x<len(a1) and y<len(a2)):
      if(a1[x]<a2[y]):
         c.append(a1[x])
         x+=1
      else:
         c.append(a2[y])
         y+=1
   while(x<len(a1)):
      c.append(a1[x])
      x+=1
   while(y<len(a2)):
      c.append(a2[y])
      y+=1
   return c

def mergesort(array):
   if(len(array)==1):
      return array
   mid=(len(array))//2
   a1=mergesort(array[:mid])
   a2=mergesort(array[mid:])
   return merge(a1,a2)
array=[2,3,1,5,4,6,8,10,7,9]
print(mergesort(array))

ผลลัพธ์

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]