Mergesort with Python

Question

I couldn't find any working Python 3.3 mergesort algorithm codes, so I made one myself. Is there any way to speed it up? It sorts 20,000 numbers in about 0.3-0.5 seconds

def msort(x):
    result = []
    if len(x) < 2:
        return x
    mid = int(len(x)/2)
    y = msort(x[:mid])
    z = msort(x[mid:])
    while (len(y) > 0) or (len(z) > 0):
        if 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)
        elif len(z) > 0:
            for i in z:
                result.append(i)
                z.pop(0)
        else:
            for i in y:
                result.append(i)
                y.pop(0)
    return result

Answer 1

although there are many great answers I'll try also to illustrate two important things, hoping that illustrations might bring some clarity:

1. merging of two sorted arrays:

i stands for S1 array counter while j stands for S2 array counter. The idea is to increase the counter of the array which provided a smaller element.

def merge(S1, S2, S):
"""
mutable impl of merging two sorted arrays S1 and S2 into sequence S.
"""
i = j = 0
while i + j < len(S):
    if j == len(S2) or i < len(S1) and S1[i] < S2[j]:
        S[i+j] = S1[i]
        i += 1
    else:
        S[i+j] = S2[j]
        j += 1

if __name__ == "__main__":
    S1 = [5, 13, 44]
    S2 = [1, 9, 28]
    result = [None] * (len(S1) + len(S2))
    merge(S1, S2, result)
    assert result == [1, 5, 9, 13, 28, 44]

2. divide and conquer the original sequence S into smaller arrays which will later get merged into smaller sorted arrays which in the end will get merged into the final sorted array. the main idea is to recursively keep chopping an array in 2 pieces until you're left with 1 element. by default, an array with 1 element is already sorted, which is the required input for the function described in step 1. top-bottom recursion flow splits arrays, while bottom-up starts the merging process of the split arrays.

def merge_sort(seq):
"""
mutable implementation of merge-sort algorithm
"""
n = len(seq)

if n < 2:
    return

mid = n // 2
s1 = seq[:mid]
s2 = seq[mid:]

merge_sort(s1)
merge_sort(s2)

merge(s1, s2, seq)

if __name__ == "__main__":
    S = [5, 44, 13, 28, 1, 9]
    merge_sort(S)
    assert S == [1, 5, 9, 13, 28, 44]

Answer 2

"""
why i posted code because I think this is the easiest  to implement merge sort 
compared to answer i found on this question
"""

def swap(L, f, l):
    if L[f] > L[l]:
        L[f], L[l] = L[l], L[f]
    return L


def mSort(L, f, l):
    mid = int((f + l) / 2)
    """ when f=l-1 it's mean we reach the last item in list when we can't more divide our list this condition apply when we are at left or right of the list
    """
    if f == l - 1 or len(L)==1:
        return swap(L,f,l)

#
    mSort(L, f, mid)
    mSort(L, mid, l)
    swap(L, f, l)

    return L


elements = [50, 3, 7, 1, 8, 11, 100, 9, 0, -1, 900, 2]

"""
i put for loop because in worst case the small item will be in the last of out list you need n time to bring it the the first item in the list

"""
Slist = []
for i in range(len(elements)):
    Slist= mSort(l, 0, len(elements) - 1)

print(Slist)

Answer 3

I would suggest to leverage Python3's protocols instead of passing a comparator here, there and everywhere.

Also a simple set of tests based Knuth's shuffle would be a decent idea to verify implementation correctness:

from abc import abstractmethod
from collections import deque


from typing import Deque, Protocol, TypeVar, List


from random import randint


class Comparable(Protocol):
    """Protocol for annotating comparable types."""

    @abstractmethod
    def __lt__(self: 'T', x: 'T') -> bool:
        pass

    @abstractmethod
    def __gt__(self: 'T', x: 'T') -> bool:
        pass


T = TypeVar('T', bound=Comparable)


def _swap(items: List[T], i: int, j: int):
    tmp = items[i]
    items[i] = items[j]
    items[j] = tmp


def knuths_shuffle(items: List[T]):
    for i in range(len(items) - 1, 1, -1):
        j = randint(0, i)
        _swap(items, i, j)
    return items


def merge(items: List[T], low: int, mid: int, high: int):
    left_q = deque(items[low: mid])
    right_q = deque(items[mid: high])

    def put(q: Deque[T]):
        nonlocal low
        items[low] = q.popleft()
        low += 1

    while left_q and right_q:
        put(left_q if left_q[0] < right_q[0] else right_q)

    def put_all(q: Deque[T]):
        while q:
            put(q)

    put_all(left_q)
    put_all(right_q)

    return items


def mergesort(items: List[T], low: int, high: int):
    if high - low <= 1:
        return
    mid = (low + high) // 2
    mergesort(items, low, mid)
    mergesort(items, mid, high)
    merge(items, low, mid, high)


def sort(items: List[T]) -> List[T]:
    """
    >>> for i in range(100):
    ...     rand = knuths_shuffle(list(range(100)))
    ...     assert sorted(rand) == sort(rand)
    """
    mergesort(items, 0, len(items))
    return items

Answer 4

1. first divide the array until it's size grater than 1(which is base condition) and do it by recursive function.

2. compare the left & right sub array value & place those value in your array.

3. check any item remain in left & right array...

   def merge_sort(my_array):

   base condition for recursively dividing the array...

    if len(my_array) > 1:
        middle = len(my_array) // 2
        left_array = my_array[:middle]
        right_array = my_array[middle:]
   

   #recursive function merge_sort(left_array) merge_sort(right_array)

        i = 0 # index of left array...
        j = 0 # index of right array...
        k = 0 # index of new array...
   
        # conquer the array and sorted like below condition
   
        while i < len(left_array) and j < len(right_array):
            if left_array[i] < right_array[j]:
                my_array[k] = left_array[i]
                i += 1
            else:
                my_array[k] = right_array[j]
                j += 1
   
            k += 1
        # checking any item remain in left sub array....
        while i < len(left_array):
            my_array[k] = left_array[i]
            i += 1
            j += 1
        # checking any item remain in right sub array....
        while j < len(right_array):
            my_array[k] = right_array[j]
            j += 1
            k += 1
   

   my_array = [11, 31, 7, 41, 101, 56, 77, 2] print("Input Array: ",my_array)

   merge_sort(my_array) print("Sorted Array: ",my_array)

Answer 5

def merge_sort(l):
    if len(l) == 1:
        if len(n)> 0:
            for i in range(len(n)):
                if n[i] > l[0]:
                    break
            else:
                i = i+1
            n.insert(i, l[0])
        else:
            n.append(l[0])
    else:
        p = len(l)//2
        a = l[:p]
        b = l[p:]
        merge_sort(a)
        merge_sort(b)

m = [3,5,2,4,1]
n = []
merge_sort(m)
print(n)

Answer 6

def splitArray(s):
    return s[:len(s)//2], s[len(s)//2:]

# the idea here is i+j should sum to n as you increment i and j, 
# but once out of bound, the next item of a or b is infinity 
# therefore, the comparison will always switch to the other array
def merge(a, b, n):
    result = [0] * n
    a = a + [float('inf')]
    b = b + [float('inf')]
    result = [0] * n
    i, j = 0, 0
    for k in range(0, n):
        if a[i] < b[j]:
            result[k] = a[i]
            i+=1
        else:
            result[k] = b[j]
            j+=1
    return result

def mergeSort(items):
    n = len(items)
    baseCase = []
    if n == 0:
        return baseCase
    if n == 1:
        baseCase.append(items[0])
        return baseCase
    if n == 2:
        if items[0] < items[1]:
            baseCase.append(items[0])
            baseCase.append(items[1])
            return baseCase
        else:
            baseCase.append(items[1])
            baseCase.append(items[0])
            return baseCase
    left, right = splitArray(items)
    sortedLeft = mergeSort(left)
    sortedRight = mergeSort(right)
    return merge(sortedLeft,sortedRight,n)

# Driver code to test above
arr = [12, 11, 13, 5, 6, 7]
n = len(arr)
print ("Given array is")
for i in range(n):
    print ("%d" %arr[i]),

arr = mergeSort(arr)
print ("\n\nSorted array is")
for i in range(n):
    print ("%d" %arr[i]),

Answer 7

Here is my attempt at the recursive merge_sort function in python. Note, this is my first python class and my first encounter with this problem so please bear with me if my code is rough, but it works.

def merge_sort(S):
    temp = []

    if len(S) < 2:
        return S

    split = len(S) // 2
    left = merge_sort(S[:split])
    right = merge_sort(S[split:])

    finale = temp + merge(left, right)

    return finale


def merge(left, right):

    holder = []

    while len(left) > 0 and len(right) > 0:

        if left[0] < right[0]:

            holder.append(left[0])
            del left[0]

        elif left[0] > right[0]:

            holder.append(right[0])
            del right[0]

    if len(left) > 0:

        holder.extend(left)

    elif len(right) > 0:

        holder.extend(right)

    return holder

Answer 8

from run_time import run_time
from random_arr import make_arr

def merge(arr1: list, arr2: list):
    temp = []
    x, y = 0, 0
    while len(arr1) and len(arr2):
        if arr1[0] < arr2[0]:
            temp.append(arr1[0])
            x += 1
            arr1 = arr1[x:]
        elif arr1[0] > arr2[0]:
            temp.append(arr2[0])
            y += 1
            arr2 = arr2[y:]
        else:
            temp.append(arr1[0])
            temp.append(arr2[0])
            x += 1
            y += 1
            arr1 = arr1[x:]
            arr2 = arr2[y:]

    if len(arr1) > 0:
        temp += arr1
    if len(arr2) > 0:
        temp += arr2
    return temp

@run_time
def merge_sort(arr: list):
    total = len(arr)
    step = 2
    while True:
        for i in range(0, total, step):
            arr[i:i + step] = merge(arr[i:i + step//2], arr[i + step//2:i + step])
        step *= 2
        if step > 2 * total:
            return arr

arr = make_arr(20000)
merge_sort(arr)
# run_time is 0.10300588607788086

Answer 9

Take my implementation

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 the sorted list.
print(merge_sort([5, 2, 6, 8, 5, 8, 1]))

Answer 10

After implementing different versions of solution, I finally made a trade-off to achieve these goals based on CLRS version.

Goal

• not using list.pop() to iterate values
• not creating a new list for saving result, modifying the original one instead
• not using float('inf') as sentinel values

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

def merge(A, p, q, r):
    L = A[p:q+1]
    R = A[q+1:r+1]
    i = 0
    j = 0
    k = p
    while i < len(L) and j < len(R):
        if(L[i] < R[j]):
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        k += 1
    if i < len(L):
        A[k:r+1] = L[i:]

if __name__ == "__main__":
    items = [6, 2, 9, 1, 7, 3, 4, 5, 8]
    mergesort(items, 0, len(items)-1)
    print items
    assert items == [1, 2, 3, 4, 5, 6, 7, 8, 9]

Reference

[1] Book: CLRS

[2] https://github.com/gzc/CLRS/blob/master/C02-Getting-Started/exercise_code/merge-sort.py

Answer 11

def merge(arr, p, q, r):
    left = arr[p:q + 1]
    right = arr[q + 1:r + 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 init_func(function):
    def wrapper(*args):
        a = []
        if len(args) == 1:
            a = args[0] + []
            function(a, 0, len(a) - 1)
        else:
            function(*args)
        return a

    return wrapper


@init_func
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, 4, 3, 2, 1]
    print(merge_sort(test))

Result would be

[1, 2, 3, 4, 5]

Answer 12

#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)   

Answer 13

Glad there are tons of answers, I hope you find this one to be clear, concise, and fast.

Thank you

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)

Answer 14

This is very similar to the "MIT" solution and a couple others above, but answers the question in a little more "Pythonic" manner by passing references to the left and right partitions instead of positional indexes, and by using a range in the for loop with slice notation to fill in the sorted array:

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

This solution finds the left and right partitions using Python's handy // operator, and then passes the left, right, and array references to the merge function, which in turn rebuilds the original array in place. The trick is in the cleanup: when you have reached the end of either the left or the right partition, the original array is filled in with whatever is left over in the other partition.

Answer 15

Code from MIT course. (with generic cooperator )

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)

Answer 16

Many have answered this question correctly, this is just another solution (although my solution is very similar to Max Montana) but I have few differences for implementation:

let's review the general idea here before we get to the code:

• Divide the list into two roughly equal halves.
• Sort the left half.
• Sort the right half.
• Merge the two sorted halves into one sorted list.

here is the code (tested with 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))

Answer 17

The first improvement would be to simplify the three cases in the main loop: Rather than iterating while some of the sequence has elements, iterate while both sequences have elements. When leaving the loop, one of them will be empty, we don't know which, but we don't care: We append them at the end of the result.

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

The second optimization is to avoid popping the elements. Rather, have two indices:

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

A final improvement consists in using a non recursive algorithm to sort short sequences. In this case I use the built-in sorted function and use it when the size of the input is less than 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

My measurements to sort a random list of 100000 integers are 2.46 seconds for the original version, 2.33 for msort2, 0.60 for msort3 and 0.40 for msort4. For reference, sorting all the list with sorted takes 0.03 seconds.

Answer 18

The following code pops at the end (efficient enough) and sorts inplace despite returning as well.

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

Answer 19

If you change your code like that it'll be working.

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]

Answer 20

    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)

Answer 21

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)

Answer 22

A little late the the party, but I figured I'd throw my hat in the ring as my solution seems to run faster than OP's (on my machine, anyway):

# [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

This doesn't have any slow pop()s, and once one of the half-arrays is exhausted, it immediately extends the other one onto the output array rather than starting a new loop.

I know it's machine dependent, but for 100,000 random elements (above merge_sort() vs. Python built-in sorted()):

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

Answer 23

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

Answer 24

Here is the CLRS Implementation:

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

Result:

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

Answer 25

As already said, l.pop(0) is a O(len(l)) operation and must be avoided, the above msort function is O(n**2). If efficiency matter, indexing is better but have cost too. The for x in l is faster but not easy to implement for mergesort : iter can be used instead here. Finally, checking i < len(l) is made twice because tested again when accessing the element : the exception mechanism (try except) is better and give a last improvement of 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

Answer 26

Try this recursive version

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()

Answer 27

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

Answer 28

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]))

Answer 29

here is another solution

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()

and here is run time for list with 100000 elements:

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

Answer 30

A longer one that counts inversions and adheres to the sorted interface. It's trivial to modify this to make it a method of an object that sorts in place.

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()

Uses

>>> 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