可视化合并排序

Question

我必须创建一个代码，让可视化合并排序的工作原理，使用 turtle 模块。这是我的代码

import turtle
from random import randint
import time

def draw_bar(x,y,w,h):
    turtle.up()
    turtle.goto(x,y)
    turtle.seth(0)
    turtle.down()
    turtle.begin_fill()
    turtle.fd(w)
    turtle.left(90)
    turtle.fd(h)
    turtle.left(90)
    turtle.fd(w)
    turtle.left(90)
    turtle.fd(h)
    turtle.left(90)
    turtle.end_fill()

def draw_bars(v,currenti=-1,currentj=-1,M=500):
    turtle.clear()
    x = -250
    n = len(v)
    w = 500/n
    r = 500/M

    for  i in range(n):
        if i == currenti: turtle.fillcolor('red')
        elif i == currentj: turtle.fillcolor('blue')
        else: turtle.fillcolor('gray')
        draw_bar(x,-250,w,v[i]*r)
        x += w
     screen.update()

def mergeSort(arr, start, length):
    if length > 1:
        mergeSort(arr, start, int(length/2))
        mergeSort(arr, start+int(length/2), int(length/2))

        L = arr[start:start+int(length/2)]
        R = arr[start+int(length/2):start+length]
        i=0
        j=0
        k=0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[start+k] = L[i]
                draw_bars(arr, j, j+1, max(arr))
                turtle.update()
                i += 1
            else:
                arr[start+k] = R[j]
                draw_bars(arr, j, j+1, max(arr))
                turtle.update()
                j += 1
            k += 1
        while i < len(L):
            arr[start+k] = L[i]
            draw_bars(arr, j, j+1, max(arr))
            turtle.update()
            i += 1
            k += 1
        while j < len(R):
            arr[start+k] = R[j]
            draw_bars(arr, j, j+1, max(arr))
            turtle.update()
            j += 1
            k += 1
    

screen = turtle.Screen()
screen.setup(600,600)
screen.tracer(0,0)
screen.title('Grafica')
turtle.speed(0)
turtle.hideturtle()
a = [randint(0,100) for i in range(90)]
mergeSort(a,0,len(a))

当我运行时，出现了一些问题，列表乱了，但好一点了。我认为归并排序算法有问题。有人知道错误吗？谁能帮我，o 尝试解释另一种方法来展示算法的工作原理？

为了达到这一点，我阅读了 geeks for geeks 页面：https://www.geeksforgeeks.org/merge-sort/, and the following question:

Answer 1

I think there is a problem in the merge sort algorithm.

问题似乎是你的半数组长度计算（用 length//2 代替 int(length/2):

mergeSort(array, start, length//2)
mergeSort(array, start + length//2, length//2)

第二个不正确，应该是：

mergeSort(array, start, length//2)
mergeSort(array, start + length//2, length - length//2)

否则你可能会在最后失去一个。

可视化合并排序

Visualize the merge sort

python

mergesort

turtle-graphics

python-turtle