Đoạn code Python bên dưới bị thiếu một số phần quan trọng.
Hãy kéo các khối code từ cột "Gợi ý" bên phải và thả vào các ô trống để hoàn thiện thuật toán.
def mergeSort(A):
n = len(A)
# 1. Trường hợp cơ bản của đệ quy
if n <= 1:
return
# 2. Chia mảng
mid = n // 2
# 3. Gọi đệ quy cho nửa bên trái
left = mergeSort()
# 4. Gọi đệ quy cho nửa bên phải
right = mergeSort()
# 5. Trộn 2 mảng đã sắp xếp
return merge(left, right)
def merge(A, B):
m, n = len(A), len(B)
C = [0] * (m + n)
i = j = k = 0
# 6. Điều kiện lặp chính khi cả 2 mảng con còn phần tử
while :
# 7. So sánh 2 phần tử đầu
if :
C[k] = A[i]
i += 1
else:
C[k] = B[j]
j += 1
k += 1
# 8. Xử lý các phần tử còn lại của mảng A hoặc B
if : # Mảng A đã hết
while j < n:
C[k] = B[j]
j += 1
k += 1
else: # Mảng B đã hết
while i < m:
C[k] = A[i]
i += 1
k += 1
return C