Сортировка слиянием (Merge sort)

@codcw · Регистрация: 22.12.2017

Author24 — интернет-сервис помощи студентам

Пытаюсь реализовать сортировку слиянием на python(без рекурсии, чтоб не запутаться). Вопрос: Как сделать мой код более правильным алгоритмически? Можно ли вообще считать то что я написал - сортировкой слиянием?

Python

def mergeSort(x):
    if len(x) < 2: return x
    y = []
    for i in range(0, len(x), 2):
        xy = x[i:i + 2]
        if xy[0] < xy[-1]:
            y.append(xy)
        else:
            y.append(xy[::-1])
    while len(y) > 1:
        c = y.pop(0)
        c.extend(y.pop(0))
        for _ in range(len(c)):
            for j in range(1, len(c)):
                if c[j - 1] > c[j]:
                    c[j - 1], c[j] = c[j], c[j - 1]
        y.append(c)
    return y[0]
 
from random import randint
 
x1 = [randint(1,21) for _ in range(10)]
print(x1, mergeSort(x1))

Добавлено через 54 минуты
и ещё один маленький дополнительный вопрос - если вызвать print(x1) ещё раз после основной программы - он будет отсортирован, как такое возможно?

Добавлено через 7 минут
ещё чуть-чуть поигрался - если вызвать print(x1) до и после последней строки(23) то всё выводит как положено
потом вернул как было - теперь x1 выводит как нужно, но для другой сортировки выводит одинаковые массивы(если вызывать в одном принте), правильно выводит только разными принтами, мне кажется что я схожу с ума

@Catstail · 21.05.2022, 10:11

Сообщение от codcw

Можно ли вообще считать то что я написал - сортировкой слиянием?

- боюсь, что нет. Меня смущают строки 13-16

Добавлено через 3 минуты
Вот несовершенный вариант сортировки слиянием:

Python

def merge(s1,s2):
    r=[]
    i,j=0,0
    while(True):
        if i>= len(s1):
            r+=s2[j:]
            break
        if j>= len(s2):
            r+=s1[i:]
            break
        if s1[i] < s2[j]:
            r+=[s1[i]]
            i+=1 
        else:
            r+=[s2[j]]
            j+=1
    return r
    
def mergeSort(x):
    xx=[]
    for a in x:
        xx=xx+[[a]]
    while(True):
        k=len(xx)
        if k==1:
            break
        yy=[]
        i=0
        j=1
        while(True):
            if i==k: 
                break
            if j==k:
                yy+=[xx[i]]
                break
            else:
                yy+=[merge(xx[i],xx[j])]
            i+=2
            j+=2
            
        xx=yy
    return xx[0]
 
z=mergeSort([1,2,3,1,2,3,1,2,3])
print(z)
 
z=mergeSort([1,3,-4,8,2,34])
print(z)

@codcw · 22.05.2022, 15:04 **[ТС]**

Catstail,

Python

def mergeSort(x):
    if len(x) < 2: return x
    y = []
    for i in range(0, len(x), 2):
        xy = x[i:i + 2]
        if xy[0] < xy[-1]:
            y.append(xy)
        else:
            y.append(xy[::-1])
    while len(y) > 1:
        r = []
        a = y.pop(0)
        b = y.pop(0)
        while True:
            if a and b:
                if a[0] < b[0]:
                    r.append(a.pop(0))
                else:
                    r.append(b.pop(0))
            else:
                if b:
                    r.extend(b)
                    break
                elif a:
                    r.extend(a)
                    break
                else:
                    break
        y.append(r)
    return y[0]
 
from random import randint
 
x1 = [randint(1,21) for _ in range(10)]
 
print(x1)
print(mergeSort(x1))

переделал
выходит, было неверно только из-за сортировки при самом слиянии? теперь всё в порядке? если да, как сделать лучше?

	22.05.2022, 15:04