Strand Sort

Strand Sort คือ อัลกอริธึมการจัดเรียงที่ทำงานได้ดีหากมีหลายรายการเรียงตามลำดับ ขั้นแรกให้เริ่มต้นรายการย่อยโดยการย้ายรายการแรกจากรายการต้นฉบับไปยังรายการย่อย สำหรับแต่ละรายการถัดไปในรายการเดิมถ้ารายการนั้นมากกว่ารายการสุดท้ายของรายการย่อยให้นำรายการนั้นออกจากรายการเดิมแล้วเพิ่มลงในรายการย่อย รวมรายการย่อยไว้ในรายการเรียงลำดับขั้นสุดท้าย แยกและรวมรายการย่อยซ้ำ ๆ จนกระทั่งรายการทั้งหมดถูกจัดเรียง จัดการสินค้าสองรายการหรือน้อยกว่าเป็นกรณีพิเศษ

การนำ Strand Sort ไปใช้งานในภาษาPython

ตัวอย่างภาษาไพทอน

def sort(array):
    if len(array) < 2:
        return array
    result = []
    while array:
        sublist = [array.pop(0)]
        leftovers = []
        last = sublist[0]
        
        sublist_append = sublist.append
        leftovers_append = leftovers.append
        for item in array:
            if item >= last:
                sublist_append(item)
                last = item
            else:
                leftovers_append(item)
        result = merge(result, sublist)
        array = leftovers
    return result


def merge(left, right):
    if not left:
        return right
    if not right:
        return left

    if left[-1] > right[-1]:
        left, right = right, left

    it = iter(right)
    y = next(it)
    result = []

    for x in left:
        while y < x:
            result.append(y)
            y = next(it)
        result.append(x)
    result.append(y)
    result.extend(it)
    return result

Strand Sort เป็นอัลกอริทึมการเรียงลำดับที่ทำงานในเวลา O (n) ถ้ารายการถูกจัดเรียงแล้วและทำงานใน O (n * n) ในกรณีที่เลวร้ายที่สุด