Слияние с Python

Ответ 1

Вы можете инициализировать весь список результатов в вызове верхнего уровня для mergesort:

result = [0]*len(x)   # replace 0 with a suitable default element if necessary. 
                      # or just copy x (result = x[:])

Тогда для рекурсивных вызовов вы можете использовать вспомогательную функцию, к которой вы передаете не подсписки, а индексы в x. И вызовы нижнего уровня считывают их значения из x и записываются непосредственно в result.

Таким образом, вы можете избежать всего этого pop ing и append ing, что должно повысить производительность.

Ответ 2

Первым улучшением было бы упростить три случая в главном цикле: вместо итерации, когда у некоторой последовательности есть элементы, итерация, когда у обеих последовательностей есть элементы. При выходе из цикла один из них будет пустым, мы не знаем, какой, но нам все равно: мы добавляем их в конец результата.

def msort2(x):
    if len(x) < 2:
        return x
    result = []          # moved!
    mid = int(len(x) / 2)
    y = msort2(x[:mid])
    z = msort2(x[mid:])
    while (len(y) > 0) and (len(z) > 0):
        if y[0] > z[0]:
            result.append(z[0])
            z.pop(0)
        else:
            result.append(y[0])
            y.pop(0)
    result += y
    result += z
    return result

Вторая оптимизация состоит в том, чтобы избежать pop элементов. Скорее, есть два индекса:

def msort3(x):
    if len(x) < 2:
        return x
    result = []
    mid = int(len(x) / 2)
    y = msort3(x[:mid])
    z = msort3(x[mid:])
    i = 0
    j = 0
    while i < len(y) and j < len(z):
        if y[i] > z[j]:
            result.append(z[j])
            j += 1
        else:
            result.append(y[i])
            i += 1
    result += y[i:]
    result += z[j:]
    return result

Последнее улучшение состоит в использовании нерекурсивного алгоритма для сортировки коротких последовательностей. В этом случае я использую встроенную функцию sorted и использую ее, когда размер ввода меньше 20:

def msort4(x):
    if len(x) < 20:
        return sorted(x)
    result = []
    mid = int(len(x) / 2)
    y = msort4(x[:mid])
    z = msort4(x[mid:])
    i = 0
    j = 0
    while i < len(y) and j < len(z):
        if y[i] > z[j]:
            result.append(z[j])
            j += 1
        else:
            result.append(y[i])
            i += 1
    result += y[i:]
    result += z[j:]
    return result

Мои измерения для сортировки случайного списка из 100000 целых чисел составляют 2,46 секунды для исходной версии, 2,33 для msort2, 0,60 для msort3 и 0,40 для msort4. Для справки, сортировка всего списка с sorted занимает 0,03 секунды.

Ответ 3

Код из курса MIT. (с общим кооператором)

import operator


def merge(left, right, compare):
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if compare(left[i], right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    while i < len(left):
        result.append(left[i])
        i += 1
    while j < len(right):
        result.append(right[j])
        j += 1
    return result


def mergeSort(L, compare=operator.lt):
    if len(L) < 2:
        return L[:]
    else:
        middle = int(len(L) / 2)
        left = mergeSort(L[:middle], compare)
        right = mergeSort(L[middle:], compare)
        return merge(left, right, compare)

Ответ 4

def merge_sort(x):

    if len(x) < 2:return x

    result,mid = [],int(len(x)/2)

    y = merge_sort(x[:mid])
    z = merge_sort(x[mid:])

    while (len(y) > 0) and (len(z) > 0):
            if y[0] > z[0]:result.append(z.pop(0))   
            else:result.append(y.pop(0))

    result.extend(y+z)
    return result

Ответ 5

Возьми мою реализацию

def merge_sort(sequence):
    """
    Sequence of numbers is taken as input, and is split into two halves, following which they are recursively sorted.
    """
    if len(sequence) < 2:
        return sequence

    mid = len(sequence) // 2     # note: 7//2 = 3, whereas 7/2 = 3.5

    left_sequence = merge_sort(sequence[:mid])
    right_sequence = merge_sort(sequence[mid:])

    return merge(left_sequence, right_sequence)

def merge(left, right):
    """
    Traverse both sorted sub-arrays (left and right), and populate the result array
    """
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]

    return result


print merge_sort([5, 2, 6, 8, 5, 8, 1])

Ответ 6

Как уже говорилось, l.pop(0) является операцией O (len (l)), и ее следует избегать, указанная выше функция msort - O (n ** 2). Если эффективность имеет значение, индексирование лучше, но также и стоимость. for x in l быстрее, но не просто реализовать для mergesort: iter можно использовать здесь. Наконец, проверка i < len(l) производится дважды, потому что снова проверяется при обращении к элементу: механизм исключения (попробуйте исключить) лучше и дает последнее улучшение на 30%.

def msort(l):
    if len(l)>1:
        t=len(l)//2
        it1=iter(msort(l[:t]));x1=next(it1)
        it2=iter(msort(l[t:]));x2=next(it2)
        l=[]
        try:
            while True:
                if x1<=x2: l.append(x1);x1=next(it1)
                else     : l.append(x2);x2=next(it2)
        except:
            if x1<=x2: l.append(x2);l.extend(it2)
            else:      l.append(x1);l.extend(it1)
    return l

Ответ 7

Такие петли, возможно, ускоряются:

for i in z:
    result.append(i)
    z.pop(0)

Вместо этого просто выполните следующее:

result.extend(z)

Обратите внимание, что нет необходимости очищать содержимое z, потому что вы все равно не будете его использовать.

Ответ 8

Более длинный, который учитывает инверсии и придерживается интерфейса sorted. Это тривиально, чтобы изменить это, чтобы сделать его методом объекта, который сортируется на месте.

import operator

class MergeSorted:

    def __init__(self):
        self.inversions = 0

    def __call__(self, l, key=None, reverse=False):

        self.inversions = 0

        if key is None:
            self.key = lambda x: x
        else:
            self.key = key

        if reverse:
            self.compare = operator.gt
        else:
            self.compare = operator.lt

        dest = list(l)
        working = [0] * len(l)
        self.inversions = self._merge_sort(dest, working, 0, len(dest))
        return dest

    def _merge_sort(self, dest, working, low, high):
        if low < high - 1:
            mid = (low + high) // 2
            x = self._merge_sort(dest, working, low, mid)
            y = self._merge_sort(dest, working, mid, high)
            z = self._merge(dest, working, low, mid, high)
            return (x + y + z)
        else:
            return 0

    def _merge(self, dest, working, low, mid, high):
        i = 0
        j = 0
        inversions = 0

        while (low + i < mid) and (mid + j < high):
            if self.compare(self.key(dest[low + i]), self.key(dest[mid + j])):
                working[low + i + j] = dest[low + i]
                i += 1
            else:
                working[low + i + j] = dest[mid + j]
                inversions += (mid - (low + i))
                j += 1

        while low + i < mid:
            working[low + i + j] = dest[low + i]
            i += 1

        while mid + j < high:
            working[low + i + j] = dest[mid + j]
            j += 1

        for k in range(low, high):
            dest[k] = working[k]

        return inversions


msorted = MergeSorted()

Использование

>>> l = [5, 2, 3, 1, 4]
>>> s = msorted(l)
>>> s
[1, 2, 3, 4, 5]
>>> msorted.inversions
6

>>> l = ['e', 'b', 'c', 'a', 'd']
>>> d = {'a': 10,
...      'b': 4,
...      'c': 2,
...      'd': 5,
...      'e': 9}
>>> key = lambda x: d[x]
>>> s = msorted(l, key=key)
>>> s
['c', 'b', 'd', 'e', 'a']
>>> msorted.inversions
5

>>> l = [5, 2, 3, 1, 4]
>>> s = msorted(l, reverse=True)
>>> s
[5, 4, 3, 2, 1]
>>> msorted.inversions
4

>>> l = ['e', 'b', 'c', 'a', 'd']
>>> d = {'a': 10,
...      'b': 4,
...      'c': 2,
...      'd': 5,
...      'e': 9}
>>> key = lambda x: d[x]
>>> s = msorted(l, key=key, reverse=True)
>>> s
['a', 'e', 'd', 'b', 'c']
>>> msorted.inversions
5

Ответ 9

Многие ответили на этот вопрос правильно, это просто другое решение (хотя мое решение очень похоже на Макса Монтана), но у меня есть несколько различий в реализации:

давайте рассмотрим общую идею здесь, прежде чем мы перейдем к коду:

• Разделите список на две примерно равные половины.
• Сортировка левой половины.
• Сортировка правой половины.
• Объедините две отсортированные половины в один отсортированный список.

Вот код (протестирован с python 3.7):

def merge(left,right):
    result=[] 
    i,j=0,0
    while i<len(left) and j<len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i+=1
        else:
            result.append(right[j])
            j+=1
    result.extend(left[i:]) # since we want to add each element and not the object list
    result.extend(right[j:])
    return result

def merge_sort(data):
    if len(data)==1:
        return data
    middle=len(data)//2
    left_data=merge_sort(data[:middle])
    right_data=merge_sort(data[middle:])
    return merge(left_data,right_data)


data=[100,5,200,3,100,4,8,9] 
print(merge_sort(data))

Ответ 10

здесь другое решение

class MergeSort(object):
    def _merge(self,left, right):
        nl = len(left)
        nr = len(right)
        result = [0]*(nl+nr)
        i=0
        j=0
        for k in range(len(result)):
            if nl>i and nr>j:
                if left[i] <= right[j]:
                    result[k]=left[i]
                    i+=1
                else:
                    result[k]=right[j]
                    j+=1
            elif nl==i:
                result[k] = right[j]
                j+=1
            else: #nr>j:
                result[k] = left[i]
                i+=1
        return result

    def sort(self,arr):
        n = len(arr)
        if n<=1:
            return arr 
        left = self.sort(arr[:n/2])
        right = self.sort(arr[n/2:] )
        return self._merge(left, right)
def main():
    import random
    a= range(100000)
    random.shuffle(a)
    mr_clss = MergeSort()
    result = mr_clss.sort(a)
    #print result

if __name__ == '__main__':
    main()

и вот время выполнения для списка со 100000 элементами:

real    0m1.073s
user    0m1.053s
sys         0m0.017s

Ответ 11

def merge(l1, l2, out=[]):
    if l1==[]: return out+l2
    if l2==[]: return out+l1
    if l1[0]<l2[0]: return merge(l1[1:], l2, out+l1[0:1])
    return merge(l1, l2[1:], out+l2[0:1])
def merge_sort(l): return (lambda h: l if h<1 else merge(merge_sort(l[:h]), merge_sort(l[h:])))(len(l)/2)
print(merge_sort([1,4,6,3,2,5,78,4,2,1,4,6,8]))

Ответ 12

Немного поздно вечеринка, но я подумал, что брошу свою шляпу в кольцо, так как мое решение работает быстрее, чем OP (на моей машине, во всяком случае):

# [Python 3]
def merge_sort(arr):
    if len(arr) < 2:
        return arr
    half = len(arr) // 2
    left = merge_sort(arr[:half])
    right = merge_sort(arr[half:])
    out = []
    li = ri = 0  # index of next element from left, right halves
    while True:
        if li >= len(left):  # left half is exhausted
            out.extend(right[ri:])
            break
        if ri >= len(right): # right half is exhausted
            out.extend(left[li:])
            break
        if left[li] < right[ri]:
            out.append(left[li])
            li += 1
        else:
            out.append(right[ri])
            ri += 1
    return out

Это не имеет медленных pop() s, и как только один из полумассировок исчерпан, он немедленно расширяет другой в выходной массив, а не запускает новый цикл.

Я знаю, что он зависит от машины, но для 100 000 случайных элементов (выше merge_sort() и встроенного Python sorted()):

merge sort: 1.03605 seconds
Python sort: 0.045 seconds
Ratio merge / Python sort: 23.0229

Ответ 13

Вот CLRS Реализация:

def merge(arr, p, q, r):
    n1 = q - p + 1
    n2 = r - q
    right, left = [], []
    for i in range(n1):
        left.append(arr[p + i])
    for j in range(n2):
        right.append(arr[q + j + 1])
    left.append(float('inf'))
    right.append(float('inf'))
    i = j = 0
    for k in range(p, r + 1):
        if left[i] <= right[j]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1


def merge_sort(arr, p, r):
    if p < r:
        q = (p + r) // 2
        merge_sort(arr, p, q)
        merge_sort(arr, q + 1, r)
        merge(arr, p, q, r)


if __name__ == '__main__':
    test = [5, 2, 4, 7, 1, 3, 2, 6]
    merge_sort(test, 0, len(test) - 1)
    print test

Результат:

[1, 2, 2, 3, 4, 5, 6, 7]

Ответ 14

def merge(x):
    if len(x) == 1:
        return x
    else:
        mid = int(len(x) / 2)
        l = merge(x[:mid])
        r = merge(x[mid:])
    i = j = 0
    result = []
    while i < len(l) and j < len(r):
        if l[i] < r[j]:
            result.append(l[i])
            i += 1
        else:
            result.append(r[j])
            j += 1
    result += l[i:]
    result += r[j:]
    return result

Ответ 15

def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)

Ответ 16

Попробуйте эту рекурсивную версию

def mergeList(l1,l2):
    l3=[]
    Tlen=len(l1)+len(l2)
    inf= float("inf")
    for i in range(Tlen):
        print   "l1= ",l1[0]," l2= ",l2[0]
        if l1[0]<=l2[0]:
            l3.append(l1[0])
            del l1[0]
            l1.append(inf)
        else:
            l3.append(l2[0])
            del l2[0]
            l2.append(inf)
    return l3

def main():
    l1=[2,10,7,6,8]
    print mergeSort(breaklist(l1))

def breaklist(rawlist):
    newlist=[]
    for atom in rawlist:
        print atom
        list_atom=[atom]
        newlist.append(list_atom)
    return newlist

def mergeSort(inputList):
    listlen=len(inputList)
    if listlen ==1:
        return inputList
    else:
        newlist=[]
        if listlen % 2==0:
            for i in range(listlen/2):
                newlist.append(mergeList(inputList[2*i],inputList[2*i+1]))
        else:
            for i in range((listlen+1)/2):
                if 2*i+1<listlen:
                    newlist.append(mergeList(inputList[2*i],inputList[2*i+1]))
                else:
                    newlist.append(inputList[2*i])
        return  mergeSort(newlist)

if __name__ == '__main__':
    main()

Ответ 17

    def merge(a,low,mid,high):
        l=a[low:mid+1]
        r=a[mid+1:high+1]
        #print(l,r)
        k=0;i=0;j=0;
        c=[0 for i in range(low,high+1)]
        while(i<len(l) and j<len(r)):
            if(l[i]<=r[j]):

                c[k]=(l[i])
                k+=1

                i+=1
            else:
                c[k]=(r[j])
                j+=1
                k+=1
        while(i<len(l)):
            c[k]=(l[i])
            k+=1
            i+=1

        while(j<len(r)):
            c[k]=(r[j])
            k+=1
            j+=1
        #print(c)  
        a[low:high+1]=c  

    def mergesort(a,low,high):
        if(high>low):
            mid=(low+high)//2


            mergesort(a,low,mid)
            mergesort(a,mid+1,high)
            merge(a,low,mid,high)

    a=[12,8,3,2,9,0]
    mergesort(a,0,len(a)-1)
    print(a)

Ответ 18

Если вы измените свой код таким образом, он будет работать.

def merge_sort(arr):
    if len(arr) < 2:
        return arr[:]
    middle_of_arr = len(arr) / 2
    left = arr[0:middle_of_arr]
    right = arr[middle_of_arr:]
    left_side = merge_sort(left)
    right_side = merge_sort(right)
    return merge(left_side, right_side)

def merge(left_side, right_side):
    result = []
    while len(left_side) > 0 or len(right_side) > 0:
        if len(left_side) > 0 and len(right_side) > 0:
            if left_side[0] <= right_side[0]:
                result.append(left_side.pop(0))
            else:
                result.append(right_side.pop(0))
        elif len(left_side) > 0:
            result.append(left_side.pop(0))
        elif len(right_side) > 0:
            result.append(right_side.pop(0))
    return result

arr = [6, 5, 4, 3, 2, 1]
# print merge_sort(arr)
# [1, 2, 3, 4, 5, 6]

Ответ 19

Следующий код выскакивает в конце (достаточно эффективно) и сортирует на месте, несмотря на возврат.

def mergesort(lis):
    if len(lis) > 1:
        left, right = map(lambda l: list(reversed(mergesort(l))), (lis[::2], lis[1::2]))
        lis.clear()
        while left and right:
            lis.append(left.pop() if left[-1] < right[-1] else right.pop())
        lis.extend(left[::-1])
        lis.extend(right[::-1])
    return lis

Ответ 20

Это очень похоже на решение "MIT" и пару других выше, но отвечает на вопрос немного более "питонски", передавая ссылки на левый и правый разделы вместо позиционных индексов, и используя диапазон в for Цикл с обозначением слайса для заполнения отсортированного массива:

def merge_sort(array):
    n = len(array)
    if n > 1:
        mid = n//2
        left = array[0:mid]
        right = array[mid:n]
        print(mid, left, right, array)
        merge_sort(left)
        merge_sort(right)
        merge(left, right, array)

def merge(left, right, array):
    array_length = len(array)
    right_length = len(right)
    left_length = len(left)
    left_index = right_index = 0
    for array_index in range(0, array_length):
        if right_index == right_length:
            array[array_index:array_length] = left[left_index:left_length]
            break
        elif left_index == left_length:
            array[array_index:array_length] = right[right_index:right_length]
            break
        elif left[left_index] <= right[right_index]:
                array[array_index] = left[left_index]
                left_index += 1
        else:
            array[array_index] = right[right_index]
            right_index += 1

array = [99,2,3,3,12,4,5]
arr_len = len(array)
merge_sort(array)
print(array)
assert len(array) == arr_len

Это решение находит левый и правый разделы с помощью удобного оператора Python //, а затем передает левые, правые и массивные ссылки в функцию слияния, которая, в свою очередь, перестраивает исходный массив на месте. Хитрость заключается в очистке: когда вы достигли конца левого или правого раздела, исходный массив заполняется тем, что осталось в другом разделе.

Ответ 21

Рад, что есть множество ответов, надеюсь, вы найдете этот ответ ясным, лаконичным и быстрым.

Спасибо

import math

def merge_array(ar1, ar2):
    c, i, j= [], 0, 0

    while i < len(ar1) and j < len(ar2):
        if  ar1[i] < ar2[j]:
            c.append(ar1[i])
            i+=1
        else:
            c.append(ar2[j])
            j+=1     
    return c + ar1[i:] + ar2[j:]

def mergesort(array):
    n = len(array)
    if n == 1:
        return array
    half_n =  math.floor(n/2)  
    ar1, ar2 = mergesort(array[:half_n]), mergesort(array[half_n:])
    return merge_array(ar1, ar2)

Ответ 22

#here is my answer using two function one for merge and another for divide and 
 #conquer 
l=int(input('enter range len'))      
c=list(range(l,0,-1))
print('list before sorting is',c)
def mergesort1(c,l,r):    
    i,j,k=0,0,0
    while (i<len(l))&(j<len(r)):
        if l[i]<r[j]:
            c[k]=l[i]
            i +=1            
        else:
            c[k]=r[j]
            j +=1
        k +=1
    while i<len(l):
        c[k]=l[i]
        i+=1
        k+=1
    while j<len(r):
        c[k]=r[j]
        j+=1
        k+=1
    return c   
def mergesort(c):
    if len(c)<2:
        return c
    else:
        l=c[0:(len(c)//2)]
        r=c[len(c)//2:len(c)]
        mergesort(l)
        mergesort(r)
    return    mergesort1(c,l,r)