forked from cmuparlay/parlaylib
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmergesort_results.txt
137 lines (137 loc) · 10.7 KB
/
mergesort_results.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
Running mergesort and mergesort_skew for various n values
-----------------------------------------------
Running for n=1
Running mergesort for n=1
Time: mergesort: 0.0000
Time: mergesort: 0.0000
Time: mergesort: 0.0000
Time: mergesort: 0.0000
Time: mergesort: 0.0000
first 10 elements: [0, 139823500783792, 0, 139823500783808, 0, 139823500783824, 0, 139823500783840, 0, 139823500783856]
Running mergesort_skew for n=1
Time: mergesort: 0.0000
Time: mergesort: 0.0000
Time: mergesort: 0.0000
Time: mergesort: 0.0000
Time: mergesort: 0.0000
first 200 elements: [0, 139740736757936, 0, 139740736757952, 0, 139740736757968, 0, 139740736757984, 0, 139740736758000, 0, 139740736758016, 0, 139740736758032, 0, 139740736758048, 0, 139740736758064, 0, 139740736758080, 0, 139740736758096, 0, 139740736758112, 0, 139740736758128, 0, 139740736758144, 0, 139740736758160, 0, 139740736758176, 0, 139740736758192, 0, 139740736758208, 0, 139740736758224, 0, 139740736758240, 0, 139740736758256, 0, 139740736758272, 0, 139740736758288, 0, 139740736758304, 0, 139740736758320, 0, 139740736758336, 0, 139740736758352, 0, 139740736758368, 0, 139740736758384, 0, 139740736758400, 0, 139740736758416, 0, 139740736758432, 0, 139740736758448, 0, 139740736758464, 0, 139740736758480, 0, 139740736758496, 0, 139740736758512, 0, 139740736758528, 0, 139740736758544, 0, 139740736758560, 0, 139740736758576, 0, 139740736758592, 0, 139740736758608, 0, 139740736758624, 0, 139740736758640, 0, 139740736758656, 0, 139740736758672, 0, 139740736758688, 0, 139740736758704, 0, 139740736758720, 0, 139740736758736, 0, 139740736758752, 0, 139740736758768, 0, 139740736758784, 0, 139740736758800, 0, 139740736758816, 0, 139740736758832, 0, 139740736758848, 0, 139740736758864, 0, 139740736758880, 0, 139740736758896, 0, 139740736758912, 0, 139740736758928, 0, 139740736758944, 0, 139740736758960, 0, 139740736758976, 0, 139740736758992, 0, 139740736759008, 0, 139740736759024, 0, 139740736759040, 0, 139740736759056, 0, 139740736759072, 0, 139740736759088, 0, 139740736759104, 0, 139740736759120, 0, 139740736759136, 0, 139740736759152, 0, 139740736759168, 0, 139740736759184, 0, 139740736759200, 0, 139740736759216, 0, 139740736759232, 0, 139740736759248, 0, 139740736759264, 0, 139740736759280, 0, 139740736759296, 0, 139740736759312, 0, 139740736759328, 0, 139740736759344, 0, 139740736759360, 0, 139740736759376, 0, 139740736759392, 0, 139740736759408, 0, 139740736759424, 0, 139740736759440, 0, 139740736759456, 0, 139740736759472, 0, 139740736759488, 0, 139740736759504, 0, 139740736759520]
Running for n=10
Running mergesort for n=10
Time: mergesort: 0.0000
Time: mergesort: 0.0000
Time: mergesort: 0.0000
Time: mergesort: 0.0000
Time: mergesort: 0.0000
first 10 elements: [0, 0, 3, 3, 5, 6, 6, 6, 8, 9]
Running mergesort_skew for n=10
Time: mergesort: 0.0000
Time: mergesort: 0.0000
Time: mergesort: 0.0000
Time: mergesort: 0.0000
Time: mergesort: 0.0000
first 200 elements: [0, 0, 2, 3, 5, 6, 6, 6, 8, 9, 0, 0, 0, 0, 0, 140040936444416, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 140040936444544, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 140040936444672, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 140040936444800, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 140040936444928, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 140040936445056, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 140040936445184, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 140040936445312, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 140040936445440, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 140040936445568, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 140040936445696, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 140040936445824, 0, 0, 0, 0, 0, 0, 0, 0]
Running for n=100
Running mergesort for n=100
Time: mergesort: 0.0000
Time: mergesort: 0.0000
Time: mergesort: 0.0000
Time: mergesort: 0.0000
Time: mergesort: 0.0000
first 10 elements: [0, 0, 0, 1, 2, 2, 4, 7, 7, 8]
Running mergesort_skew for n=100
Time: mergesort: 0.0000
Time: mergesort: 0.0000
Time: mergesort: 0.0000
Time: mergesort: 0.0000
Time: mergesort: 0.0000
first 200 elements: [0, 0, 0, 0, 1, 1, 3, 4, 5, 5, 5, 7, 9, 9, 10, 11, 13, 13, 14, 15, 15, 17, 17, 18, 19, 20, 21, 21, 21, 21, 22, 23, 23, 24, 25, 26, 26, 26, 26, 29, 30, 37, 37, 40, 42, 42, 42, 43, 43, 43, 44, 49, 49, 51, 52, 54, 54, 55, 55, 56, 56, 56, 57, 57, 58, 60, 61, 63, 64, 64, 65, 65, 65, 66, 67, 67, 67, 68, 71, 72, 72, 74, 79, 80, 81, 81, 81, 81, 84, 85, 87, 88, 89, 90, 91, 91, 92, 93, 94, 98, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 140328026369152, 0, 0, 0, 1, 1, 4, 5, 5, 10, 13, 14, 15, 20, 21, 21, 21, 21, 22, 23, 26, 26, 37, 40, 42, 43, 43, 44, 54, 55, 55, 56, 56, 57, 58, 60, 64, 64, 66, 67, 67, 71, 79, 81, 81, 88, 89, 90, 92, 93, 94, 0, 3, 5, 7, 9, 9, 11, 13, 15, 17, 17, 18, 19, 23, 24, 25, 26, 26, 29, 30, 37, 42]
Running for n=1000
Running mergesort for n=1000
Time: mergesort: 0.0036
Time: mergesort: 0.0009
Time: mergesort: 0.0001
Time: mergesort: 0.0001
Time: mergesort: 0.0001
first 10 elements: [1, 1, 2, 5, 5, 5, 6, 7, 9, 10]
Running mergesort_skew for n=1000
Time: mergesort: 0.0038
Time: mergesort: 0.0012
Time: mergesort: 0.0016
Time: mergesort: 0.0001
Time: mergesort: 0.0001
first 200 elements: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 22, 22, 22]
Running for n=10000
Running mergesort for n=10000
Time: mergesort: 0.0061
Time: mergesort: 0.0014
Time: mergesort: 0.0004
Time: mergesort: 0.0004
Time: mergesort: 0.0003
first 10 elements: [0, 2, 2, 2, 3, 7, 8, 8, 9, 12]
Running mergesort_skew for n=10000
Time: mergesort: 0.0063
Time: mergesort: 0.0003
Time: mergesort: 0.0003
Time: mergesort: 0.0003
Time: mergesort: 0.0003
first 200 elements: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
Running for n=100000
Running mergesort for n=100000
Time: mergesort: 0.0105
Time: mergesort: 0.0026
Time: mergesort: 0.0027
Time: mergesort: 0.0060
Time: mergesort: 0.0025
first 10 elements: [0, 0, 1, 1, 2, 3, 3, 4, 4, 5]
Running mergesort_skew for n=100000
Time: mergesort: 0.0109
Time: mergesort: 0.0024
Time: mergesort: 0.0024
Time: mergesort: 0.0025
Time: mergesort: 0.0024
first 200 elements: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Running for n=1000000
Running mergesort for n=1000000
Time: mergesort: 0.0398
Time: mergesort: 0.0200
Time: mergesort: 0.0190
Time: mergesort: 0.0188
Time: mergesort: 0.0186
first 10 elements: [0, 0, 2, 2, 2, 5, 6, 8, 8, 8]
Running mergesort_skew for n=1000000
Time: mergesort: 0.0338
Time: mergesort: 0.0246
Time: mergesort: 0.0199
Time: mergesort: 0.0165
Time: mergesort: 0.0163
first 200 elements: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Running for n=10000000
Running mergesort for n=10000000
Time: mergesort: 0.2108
Time: mergesort: 0.2031
Time: mergesort: 0.2015
Time: mergesort: 0.1979
Time: mergesort: 0.2078
first 10 elements: [0, 0, 0, 3, 5, 5, 6, 6, 6, 6]
Running mergesort_skew for n=10000000
Time: mergesort: 0.2317
Time: mergesort: 0.1828
Time: mergesort: 0.1808
Time: mergesort: 0.1716
Time: mergesort: 0.1661
first 200 elements: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Running for n=100000000
Running mergesort for n=100000000
Time: mergesort: 2.2725
Time: mergesort: 2.1935
Time: mergesort: 2.1791
Time: mergesort: 2.1740
Time: mergesort: 2.2557
first 10 elements: [0, 0, 0, 2, 2, 3, 3, 4, 5, 5]
Running mergesort_skew for n=100000000
Time: mergesort: 1.8472
Time: mergesort: 1.7459
Time: mergesort: 1.7359
Time: mergesort: 1.7283
Time: mergesort: 1.7385
first 200 elements: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]