Natural Merge Sort无法正确排序列表最后两个元素求助

我在Python中实现自然归并排序时，get_sorted_run_length函数的所有测试用例均通过，但natural_merge_sort函数仅能正确排序列表的大部分元素，最后两个整数始终无法完成排序。测试后的结果显示，排序后的列表末尾出现未排序的元素：[10, 18, 26, 39, 54, 71, 73, 89, 92, 99, 22, 64]。

main.py #

import sys

from NaturalMergeSorter import NaturalMergeSorter
from RunLengthTestCase import RunLengthTestCase

def main():
    # Test case list: A completely sorted lst
    list1 = [15, 23, 23, 23, 31, 64, 77, 87, 88, 91]
    # Test case list: Sorted run of 3 followed by sorted run of 6
    list2 = [64, 88, 91, 12, 21, 34, 43, 56, 65]

    # Test case list: 5 elements in descending order, so 5 runs of length 1
    list3 = [-10, -20, -30, -40, -50]

    # Test case list: 8 equal elements, so 1 run of 8
    list4 = [-99, -99, -99, -99, -99, -99, -99, -99]

    test_cases = [
        # First test case uses an out-of-bounds starting index. remaining test
        # cases do not.
        RunLengthTestCase(list1, len(list1), 0),
        RunLengthTestCase(list1, 0, len(list1)),
        RunLengthTestCase(list1, 3, len(list1) - 3),
        RunLengthTestCase(list2, 0, 3),
        RunLengthTestCase(list2, 2, 1),
        RunLengthTestCase(list2, 3, 6),
        RunLengthTestCase(list3, 0, 1),
        RunLengthTestCase(list3, 3, 1),
        RunLengthTestCase(list4, 0, len(list4)),
        RunLengthTestCase(list4, 4, len(list4) - 4),
        RunLengthTestCase(list4, 5, len(list4) - 5),
    ]

    for test in (test_cases):
        # Execute the test case, printing messages to sys.stdout
        test.execute(sys.stdout)

    # Test case lst for sorting
    list5 = [92, 71, 18, 26, 54, 73, 89, 10, 39, 99, 64, 22]
    list5_copy = list(list5)
    sorter = NaturalMergeSorter()
    sorter.natural_merge_sort(list5_copy)
    print(f"""
{'PASS' if list5_copy == sorted(list5) else 'FAIL'}: NaturalMergeSort()
   List before calling natural_merge_sort(): {list5}
   List after calling natural_merge_sort():  {list5_copy}""")

if __name__ == '__main__':  
    main()

RunLengthTestCase.py #

from NaturalMergeSorter import NaturalMergeSorter

class RunLengthTestCase:
    def __init__(self, lst, start, expected_return):
        self.lst = lst
        self.start = start
        self.expected_return = expected_return

    # Executes the test case. If the test case passes, a message that starts
    # with "PASS" is printed and true is returned. Otherwise a message that
    # starts with "FAIL" is printed and false is returned.
    def execute(self, test_feedback):
        user_sorter = NaturalMergeSorter()

        # Call the get_sorted_run_length() function with the test case parameters
        user_ret_val = user_sorter.get_sorted_run_length(self.lst, self.start)

        # The test passed only if the actual return value equals the
        # expected return value
        passed = user_ret_val == self.expected_return

        if user_ret_val == self.expected_return:
            print(f"""PASS: get_sorted_run_length()\n   List: {self.lst}""", file=test_feedback)
            print(f"""   Start index:           {self.start}""", file=test_feedback)
            print(f"""   Expected return value: {self.expected_return}""", file=test_feedback)
            print(f"""   Actual return value:   {user_ret_val}""", file=test_feedback)
            return True
        else:
            print(f"""FAIL: get_sorted_run_length()\n   List: {self.lst}""", file=test_feedback)
            print(f"""   Start index:           {self.start}""", file=test_feedback)
            print(f"""   Expected return value: {self.expected_return}""", file=test_feedback)
            print(f"""   Actual return value:   {user_ret_val}""", file=test_feedback)
            return False

NaturalMergeSorter.py #

class NaturalMergeSorter:
    def __init__(self):
        return

    def get_sorted_run_length(self, integer_list, start_index):
        if start_index < 0 or start_index >= len(integer_list):
            return 0
        r_length = 1 
        cur_index = start_index
        while cur_index < len(integer_list) - 1 and integer_list[cur_index] <= integer_list[cur_index + 1]:
            r_length += 1
            cur_index += 1
        return r_length

    def natural_merge_sort(self, integer_list):
        i = 0
        while i < len(integer_list):
            r1 = self.get_sorted_run_length(integer_list, i)
            
            if i + r1 == len(integer_list):
                break

            r2 = self.get_sorted_run_length(integer_list, i + r1)

            self.merge(integer_list, i, i + r1 - 1, i + r1 + r2 - 1)

            if i + r1 + r2 == len(integer_list):
                i = 0
            else:
                i = i + r1 + r2

    def merge(self, numbers, left_first, left_last, right_last):
        merged_size = right_last - left_first + 1

        merged_numbers = [None] * merged_size
        merge_pos = 0
        left_pos = left_first
        right_pos = left_last + 1

        while left_pos <= left_last and right_pos <= right_last:
            if numbers[left_pos] <= numbers[right_pos]:
                merged_numbers[merge_pos] = numbers[left_pos]
                left_pos += 1
            else:
                merged_numbers[merge_pos] = numbers[right_pos]
                right_pos += 1

            merge_pos += 1

        while left_pos <= left_last:
            merged_numbers[merge_pos] = numbers[left_pos]
            left_pos += 1
            merge_pos += 1

        # If right partition isn't empty, add remaining elements to merged_numbers
        while right_pos <= right_last:
            merged_numbers[merge_pos] = numbers[right_pos]
            right_pos += 1
            merge_pos += 1

        # Copy merged numbers back to numbers
        for merge_pos in range(merged_size):
            numbers[left_first + merge_pos] = merged_numbers[merge_pos]

测试结果 #

PASS: get_sorted_run_length()
   List: [15, 23, 23, 23, 31, 64, 77, 87, 88, 91]
   Start index:           10
   Expected return value: 0
   Actual return value:   0
PASS: get_sorted_run_length()
   List: [15, 23, 23, 23, 31, 64, 77, 87, 88, 91]
   Start index:           0
   Expected return value: 10
   Actual return value:   10
PASS: get_sorted_run_length()
   List: [15, 23, 23, 23, 31, 64, 77, 87, 88, 91]
   Start index:           3
   Expected return value: 7
   Actual return value:   7
PASS: get_sorted_run_length()
   List: [64, 88, 91, 12, 21, 34, 43, 56, 65]
   Start index:           0
   Expected return value: 3
   Actual return value:   3
PASS: get_sorted_run_length()
   List: [64, 88, 91, 12, 21, 34, 43, 56, 65]
   Start index:           2
   Expected return value: 1
   Actual return value:   1
PASS: get_sorted_run_length()
   List: [64, 88, 91, 12, 21, 34, 43, 56, 65]
   Start index:           3
   Expected return value: 6
   Actual return value:   6
PASS: get_sorted_run_length()
   List: [-10, -20, -30, -40, -50]
   Start index:           0
   Expected return value: 1
   Actual return value:   1
PASS: get_sorted_run_length()
   List: [-10, -20, -30, -40, -50]
   Start index:           3
   Expected return value: 1
   Actual return value:   1
PASS: get_sorted_run_length()
   List: [-99, -99, -99, -99, -99, -99, -99, -99]
   Start index:           0
   Expected return value: 8
   Actual return value:   8
PASS: get_sorted_run_length()
   List: [-99, -99, -99, -99, -99, -99, -99, -99]
   Start index:           4
   Expected return value: 4
   Actual return value:   4
PASS: get_sorted_run_length()
   List: [-99, -99, -99, -99, -99, -99, -99, -99]
   Start index:           5
   Expected return value: 3
   Actual return value:   3

FAIL: NaturalMergeSort()
   List before calling natural_merge_sort(): [92, 71, 18, 26, 54, 73, 89, 10, 39, 99, 64, 22]
   List after calling natural_merge_sort():  [10, 18, 26, 39, 54, 71, 73, 89, 92, 99, 22, 64]

问题分析与修复 #

问题原因 #

当前natural_merge_sort的循环逻辑存在缺陷：当遍历到列表末尾只剩单个有序run时，直接执行break退出循环，而没有检查整个列表是否已经完全合并为一个有序run。在测试案例中，最后两个元素22和64形成的run，在之前的合并轮次中没有被与前面的大run合并，导致最终残留未排序的元素。

修复代码 #

修改natural_merge_sort函数，通过循环直到整个列表只有一个有序run为止：

def natural_merge_sort(self, integer_list):
    while True:
        i = 0
        merged = False
        while i < len(integer_list):
            r1 = self.get_sorted_run_length(integer_list, i)
            if i + r1 >= len(integer_list):
                break
            r2 = self.get_sorted_run_length(integer_list, i + r1)
            self.merge(integer_list, i, i + r1 - 1, i + r1 + r2 - 1)
            merged = True
            i += r1 + r2
        if not merged:
            break

修复说明 #

1. 外层循环持续执行，直到某次遍历中没有发生任何合并操作（说明列表已经完全有序）。
2. 内层循环遍历列表，合并每一对相邻的有序run，并标记merged为True表示进行了合并。
3. 当某次外层循环中没有合并发生，退出循环，此时列表已完全排序。

修复后，测试案例中的列表将被正确排序为[10, 18, 22, 26, 39, 54, 64, 71, 73, 89, 92, 99]。

内容的提问来源于stack exchange，提问作者pokemonmater940