Sorting seems to be slower with 2 threads instead of 1 I'm implementing a simple merge sort to practice with Python's Threads. I've tried to split the job into two threads, that sort normally, then I can join them and merge the result. However, it takes almost twice as long with two threads than it does with the "normal" algorithm. Did I do something wrong or is it normal ? How can I improve this code to make it run faster with two threads ? What advice would you give me ? Thanks a lot.



CODE

# -*- encoding: utf-8 -*-

from collections import deque
from random import randint
from time import clock
from itertools import islice
from threading import Thread

sort_dict = dict()

def merge(da, db):
    res = deque()
    a = da.popleft()
    b = db.popleft()
    while True:
        if a &lt; b:
            res.append(a)
            try:
                a = da.popleft()
            except IndexError:
                res.append(b)
                res.extend(db)
                break
        else:
            res.append(b)
            try:
                b = db.popleft()
            except IndexError:
                res.append(a)
                res.extend(da)
                break
    return res

def sort(d, put_in_global = False, nb = 0):
    l = len(d)
    if l &lt;= 1:
        return d
    else:
        da = deque(islice(d, 0, l/2))
        db = deque(islice(d, l/2, l))
        sda = sort(da)
        sdb = sort(db)
        if put_in_global:
            sort_dict[nb] = merge(sda, sdb)
        else:
            return merge(sda, sdb)

def multi_sort(d):
    l = len(d)
    if l &lt;= 1:
        return d
    else:
        da = deque(islice(d, 0, l/2))
        db = deque(islice(d, l/2, l))
        sda = Thread(target=sort, args=(da, True, 1))
        sdb = Thread(target=sort, args=(db, True, 2))
        sda.start()
        sdb.start()
        sda.join()
        sdb.join() 
        return merge(sort_dict[1], sort_dict[2])

def check_sorted(d):
    if d:
        s = d.popleft()
    while True:
        try:
            f = s
            s = d.popleft()
            if f &gt; s:
                return False
        except IndexError:
            return True


if __name__=='__main__':
    with open('results.txt', 'wb') as f:
        lengths = [2*10**i for i in xrange(1, 7)]
        f.writelines(['Length  One_time  Multi_time  Ratio\r\n'])
        for length in lengths:
            print '----------------------------'
            print 'List length : ' + str(length)
            lst = [randint(0, 10**4) for i in xrange(length)]
            # print 'List : ' + str(lst)
            print 'ONE THREAD'
            start = clock()
            res = sort(lst)
            one_time = clock() - start
            print 'Sorting time (s) : ' + str(one_time)
            print 'Sort checking : ' + str(check_sorted(res))
            print 'MULTIPLE THREAD'
            start = clock()
            res = multi_sort(lst)
            multi_time = clock() - start
            print 'Sorting time (s) : ' + str(multi_time)
            print 'Sort checking : ' + str(check_sorted(res))
            print 'CONCLUSION'
            print 'Time ratio multi/one : ' + str(multi_time/one_time)
            f.writelines([str(length)+'  '+
                          str(one_time)+'  '+
                          str(multi_time)+'  '+
                          str(multi_time/one_time)+'\r\n'
                          ])




results.txt (changed the display a little bit because it was ugly)

Length  One_time          Multi_time        Ratio
20      0.00010350001112  0.00121833484164  11.7713498623
200     0.00101618192736  0.00266847549331  2.62598204265
2000    0.0117950095317   0.0210672419328   1.7861148714
20000   0.134505249988    0.2356253311      1.7517928194
200000  1.46486474003     2.59513874989     1.77158933448
2000000 16.4877353912     31.8037152227     1.92893168577
This looks like a case of GIL. For actual multiprocessing you should use the multiprocessing module.


  multiprocessing is a package that supports spawning processes using an API similar to the threading module. The multiprocessing package offers both local and remote concurrency, effectively side-stepping the Global Interpreter Lock by using subprocesses instead of threads. Due to this, the multiprocessing module allows the programmer to fully leverage multiple processors on a given machine. It runs on both Unix and Windows.