Algorithms: Majority element

Question

I am writing a divide-and-conquer solution to the majority element problem, in which it must output 1 if there is an element in a sequence of n integers that appears more than n/2 times or 0 otherwise. My code works perfectly for any test case I can think of, but the grading system keeps saying that it provides wrong answer for a test case.

n = int(input())
array = input().split()
for i in range(n):
    array[i] = int(array[i])
def merge(alist, blist):
    a = len(alist)
    b = len(blist)
    n = a + b
    result = []
    for i in range(n):
        if len(alist) > 0 and len(blist) > 0:
            if alist[0] < blist[0]:
                result.append(alist[0])
                alist.pop(0)
            else:
                result.append(blist[0])
                blist.pop(0)
        elif len(alist) == 0:
            result.extend(blist)
        elif len(blist) == 0:
            result.extend(alist)
    return result
def mergesort(numbers):
    if len(numbers) > 1:
        n = len(numbers)
        alist = numbers[:(n//2)]
        blist = numbers[(n//2):]
        alist = mergesort(alist)
        blist = mergesort(blist)
        numbers = merge(alist, blist)
    return numbers
array = mergesort(array)
key = array[n//2]
count = 0
for i in range(n):
    if array[i] == key:
        count += 1
if count > (n//2):
    print(1)
else:
    print(0)

Could anyone show me the error in my code?

Answer 1

Expanding comment to answer:

In the merge function, when handling the case of one list being exhausted, the other list is added to the end of the combined list with extend, but the loop is not terminated, and the non-empty list is not cleared, so if the terminal extend occurs early, the remainder of the non-empty list is repeated multiple times. Change the loop to the following, with a terminal case that extends the remaining list (additional cleanups added to reduce code length):

# Stop when first list exhausted, not after fixed repetitions
while alist and blist:
    if alist[0] < blist[0]:
        result.append(alist.pop(0))
    else:
        result.append(blist.pop(0))

# Only one will have contents, simpler to just unconditionally extend,
# rather than test and extend, since extending with empty list is harmless
result += alist
result += blist

Side-note: pop(0) is O(n) on lists, while .pop() is O(1). For large sorts, the following would be more efficient:

# Reverse once up front, so you can pop from right, not left
alist.reverse()
blist.reverse()

# Stop when first list exhausted, not after fixed repetitions
while alist and blist:
    if alist[-1] < blist[-1]:
        result.append(alist.pop())
    else:
        result.append(blist.pop())

# Only one will have contents, simpler to just unconditionally extend,
# rather than test and extend, since extending with empty list is harmless
result += alist[::-1]
result += blist[::-1]