Microsoft Windows XP [Version 5.1.2600]
(C) Copyright 1985-2001 Microsoft Corp.

c:\ron\mit\classes\6.006\trunk\07spring\docdist>python -i
python -i
Python 2.5.1 (r251:54863, Apr 18 2007, 08:51:08) [MSC v.1310 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> from mergesort import *
>>> random_list(6)
[375085235, 85674444, 305677844, 501627056, 516180923, 681445716]
>>> merge_sort(_)
[85674444, 305677844, 375085235, 501627056, 516180923, 681445716]
>>> random_list(7)
[200835545, 96398376, 775302424, 544250019, 126709752, 760744248, 828091644]
>>> merge_sort(_)
[96398376, 126709752, 200835545, 544250019, 760744248, 775302424, 828091644]
>>> test_merge(2**15)
1.06196 seconds elapsed for n = 32768 (= 2.16057e-006 * n lg(n))
>>> test(test_merge)
2.9054e-005 seconds elapsed for n = 2 (= 1.4527e-005 * n lg(n))
5.14032e-005 seconds elapsed for n = 4 (= 6.4254e-006 * n lg(n))
0.000104203 seconds elapsed for n = 8 (= 4.3418e-006 * n lg(n))
0.000222654 seconds elapsed for n = 16 (= 3.47897e-006 * n lg(n))
0.000498667 seconds elapsed for n = 32 (= 3.11667e-006 * n lg(n))
0.00155662 seconds elapsed for n = 64 (= 4.0537e-006 * n lg(n))
0.00236455 seconds elapsed for n = 128 (= 2.639e-006 * n lg(n))
0.00622398 seconds elapsed for n = 256 (= 3.03905e-006 * n lg(n))
0.0123147 seconds elapsed for n = 512 (= 2.67246e-006 * n lg(n))
0.0258167 seconds elapsed for n = 1024 (= 2.52116e-006 * n lg(n))
0.0524449 seconds elapsed for n = 2048 (= 2.32799e-006 * n lg(n))
0.112032 seconds elapsed for n = 4096 (= 2.2793e-006 * n lg(n))
0.23302 seconds elapsed for n = 8192 (= 2.18806e-006 * n lg(n))
0.498367 seconds elapsed for n = 16384 (= 2.17271e-006 * n lg(n))
1.05586 seconds elapsed for n = 32768 (= 2.14816e-006 * n lg(n))
2.17603 seconds elapsed for n = 65536 (= 2.07522e-006 * n lg(n))
4.60132 seconds elapsed for n = 131072 (= 2.06502e-006 * n lg(n))
9.70674 seconds elapsed for n = 262144 (= 2.05713e-006 * n lg(n))
20.3621 seconds elapsed for n = 524288 (= 2.04408e-006 * n lg(n))
>>> test_merge(2**20)
43.1835 seconds elapsed for n = 1048576 (= 2.05915e-006 * n lg(n))
>>> test_insertion(2**11)
0.761215 seconds elapsed for n = 2048 (= 1.81488e-007 * n**2)
>>> test(test_insertion)
1.84381e-005 seconds elapsed for n = 2 (= 4.60952e-006 * n**2)
1.84381e-005 seconds elapsed for n = 4 (= 1.15238e-006 * n**2)
2.57016e-005 seconds elapsed for n = 8 (= 4.01587e-007 * n**2)
7.51492e-005 seconds elapsed for n = 16 (= 2.93552e-007 * n**2)
0.00030367 seconds elapsed for n = 32 (= 2.96553e-007 * n**2)
0.000841727 seconds elapsed for n = 64 (= 2.055e-007 * n**2)
0.00378624 seconds elapsed for n = 128 (= 2.31093e-007 * n**2)
0.0109377 seconds elapsed for n = 256 (= 1.66896e-007 * n**2)
0.0527316 seconds elapsed for n = 512 (= 2.01155e-007 * n**2)
0.208961 seconds elapsed for n = 1024 (= 1.99281e-007 * n**2)
0.762698 seconds elapsed for n = 2048 (= 1.81841e-007 * n**2)
3.03518 seconds elapsed for n = 4096 (= 1.80911e-007 * n**2)
11.9918 seconds elapsed for n = 8192 (= 1.78692e-007 * n**2)
49.4724 seconds elapsed for n = 16384 (= 1.84299e-007 * n**2)
>>> test_sorted(2**19)
1.2147 seconds elapsed for n = 524288 (= 1.2194e-007 * n lg(n))
>>> test(test_sorted)
1.53651e-005 seconds elapsed for n = 2 (= 7.68254e-006 * n lg(n))
1.25714e-005 seconds elapsed for n = 4 (= 1.57143e-006 * n lg(n))
1.39683e-005 seconds elapsed for n = 8 (= 5.82011e-007 * n lg(n))
1.67619e-005 seconds elapsed for n = 16 (= 2.61905e-007 * n lg(n))
2.65397e-005 seconds elapsed for n = 32 (= 1.65873e-007 * n lg(n))
5.16825e-005 seconds elapsed for n = 64 (= 1.3459e-007 * n lg(n))
0.000103086 seconds elapsed for n = 128 (= 1.15051e-007 * n lg(n))
0.000233549 seconds elapsed for n = 256 (= 1.14038e-007 * n lg(n))
0.000515708 seconds elapsed for n = 512 (= 1.11916e-007 * n lg(n))
0.00112864 seconds elapsed for n = 1024 (= 1.10218e-007 * n lg(n))
0.0024031 seconds elapsed for n = 2048 (= 1.06672e-007 * n lg(n))
0.00534034 seconds elapsed for n = 4096 (= 1.0865e-007 * n lg(n))
0.0119619 seconds elapsed for n = 8192 (= 1.12322e-007 * n lg(n))
0.0255021 seconds elapsed for n = 16384 (= 1.1118e-007 * n lg(n))
0.0541541 seconds elapsed for n = 32768 (= 1.10177e-007 * n lg(n))
0.117937 seconds elapsed for n = 65536 (= 1.12474e-007 * n lg(n))
0.252508 seconds elapsed for n = 131072 (= 1.13323e-007 * n lg(n))
0.548566 seconds elapsed for n = 262144 (= 1.16256e-007 * n lg(n))
1.21725 seconds elapsed for n = 524288 (= 1.22196e-007 * n lg(n))
2.715 seconds elapsed for n = 1048576 (= 1.29461e-007 * n lg(n))
5.9922 seconds elapsed for n = 2097152 (= 1.36062e-007 * n lg(n))
>>> test_merge(2**15)
1.06614 seconds elapsed for n = 32768 (= 2.16906e-006 * n lg(n))
>>> test(test_merge)
2.87746e-005 seconds elapsed for n = 2 (= 1.43873e-005 * n lg(n))
4.72127e-005 seconds elapsed for n = 4 (= 5.90159e-006 * n lg(n))
0.00010113 seconds elapsed for n = 8 (= 4.21376e-006 * n lg(n))
0.000220419 seconds elapsed for n = 16 (= 3.44405e-006 * n lg(n))
0.000488889 seconds elapsed for n = 32 (= 3.05556e-006 * n lg(n))
0.00169435 seconds elapsed for n = 64 (= 4.41237e-006 * n lg(n))
0.00236119 seconds elapsed for n = 128 (= 2.63526e-006 * n lg(n))
0.00508724 seconds elapsed for n = 256 (= 2.484e-006 * n lg(n))
0.0110408 seconds elapsed for n = 512 (= 2.396e-006 * n lg(n))
0.0255127 seconds elapsed for n = 1024 (= 2.49148e-006 * n lg(n))
0.0521362 seconds elapsed for n = 2048 (= 2.31429e-006 * n lg(n))
0.112125 seconds elapsed for n = 4096 (= 2.28118e-006 * n lg(n))
0.237232 seconds elapsed for n = 8192 (= 2.22761e-006 * n lg(n))
0.502528 seconds elapsed for n = 16384 (= 2.19085e-006 * n lg(n))
1.06425 seconds elapsed for n = 32768 (= 2.16521e-006 * n lg(n))
2.27258 seconds elapsed for n = 65536 (= 2.1673e-006 * n lg(n))
4.8815 seconds elapsed for n = 131072 (= 2.19076e-006 * n lg(n))
10.0849 seconds elapsed for n = 262144 (= 2.13727e-006 * n lg(n))
21.2105 seconds elapsed for n = 524288 (= 2.12926e-006 * n lg(n))
>>> test(test_insertion)
1.81587e-005 seconds elapsed for n = 2 (= 4.53968e-006 * n**2)
1.78794e-005 seconds elapsed for n = 4 (= 1.11746e-006 * n**2)
2.87746e-005 seconds elapsed for n = 8 (= 4.49603e-007 * n**2)
6.22984e-005 seconds elapsed for n = 16 (= 2.43353e-007 * n**2)
0.000220419 seconds elapsed for n = 32 (= 2.15253e-007 * n**2)
0.00102443 seconds elapsed for n = 64 (= 2.50105e-007 * n**2)
0.00308363 seconds elapsed for n = 128 (= 1.8821e-007 * n**2)
0.0119529 seconds elapsed for n = 256 (= 1.82387e-007 * n**2)
0.0512029 seconds elapsed for n = 512 (= 1.95323e-007 * n**2)
0.179041 seconds elapsed for n = 1024 (= 1.70747e-007 * n**2)
0.7737 seconds elapsed for n = 2048 (= 1.84464e-007 * n**2)
3.05282 seconds elapsed for n = 4096 (= 1.81962e-007 * n**2)
12.2845 seconds elapsed for n = 8192 (= 1.83053e-007 * n**2)
48.6363 seconds elapsed for n = 16384 (= 1.81185e-007 * n**2)
>>> test(test_sorted)
1.50857e-005 seconds elapsed for n = 2 (= 7.54286e-006 * n lg(n))
1.22921e-005 seconds elapsed for n = 4 (= 1.53651e-006 * n lg(n))
1.31302e-005 seconds elapsed for n = 8 (= 5.4709e-007 * n lg(n))
1.78794e-005 seconds elapsed for n = 16 (= 2.79365e-007 * n lg(n))
3.01714e-005 seconds elapsed for n = 32 (= 1.88571e-007 * n lg(n))
5.14032e-005 seconds elapsed for n = 64 (= 1.33862e-007 * n lg(n))
0.000108952 seconds elapsed for n = 128 (= 1.21599e-007 * n lg(n))
0.000229359 seconds elapsed for n = 256 (= 1.11992e-007 * n lg(n))
0.000529676 seconds elapsed for n = 512 (= 1.14947e-007 * n lg(n))
0.00115154 seconds elapsed for n = 1024 (= 1.12455e-007 * n lg(n))
0.00243215 seconds elapsed for n = 2048 (= 1.07961e-007 * n lg(n))
0.00565212 seconds elapsed for n = 4096 (= 1.14993e-007 * n lg(n))
0.0121555 seconds elapsed for n = 8192 (= 1.1414e-007 * n lg(n))
0.0259798 seconds elapsed for n = 16384 (= 1.13263e-007 * n lg(n))
0.0535012 seconds elapsed for n = 32768 (= 1.08848e-007 * n lg(n))
0.120697 seconds elapsed for n = 65536 (= 1.15106e-007 * n lg(n))
0.257051 seconds elapsed for n = 131072 (= 1.15362e-007 * n lg(n))
0.556071 seconds elapsed for n = 262144 (= 1.17847e-007 * n lg(n))
1.22675 seconds elapsed for n = 524288 (= 1.23149e-007 * n lg(n))
2.71517 seconds elapsed for n = 1048576 (= 1.29469e-007 * n lg(n))
6.03326 seconds elapsed for n = 2097152 (= 1.36994e-007 * n lg(n))
>>>