Results

Methods and measurement

For energy measurement we use the RAPL counters of the linux powercap kernel module, see lib_energy.h and lib_energy.c. All measurements reported here are done on an Intel i7-7700 CPU under ubuntu.20.04 with the 5.13.0-44-generic kernel and compiling our testbed with gcc.9.4.0. The CPU is run with hyper-threading switched of in the bios. The algorithms are measured on the following input data patterns:

• permut: randomly permuted numbers from \(1 \dots n\)
• tielog2: random sample of \(\log_2{n}\) distinct values
• ascall: \(n\) distinct ascending numbers
• asclocal: \(n\) distinct numbers randomly put into \(\sqrt{n}\) presorted sequences of length \(\sqrt{n}\)
• ascglobal: \(n\) distinct numbers cut into ascending \(\sqrt{n}\) quantiles of length \(\sqrt{n}\) and randomly permuted per quantile

Measurements for these 5 patterns are averaged to a TOTAL KPI for ranking of algorithms. Furthermore the following 3 patterns are measured

• descall: \(n\) distinct descending numbers
• desclocal: \(n\) distinct numbers randomly put into \(\sqrt{n}\) reverse-sorted sequences of length \(\sqrt{n}\)
• descglobal: \(n\) distinct numbers cut into descending \(\sqrt{n}\) quantiles of length \(\sqrt{n}\) and randomly permuted per quantile

The descending patterns are interesting with regard of the symmetry of adaptivity, but not included in the TOTAL KPI. We believe that adaptivity to ascending data is more important than to descending, furthermore, including them would give too much weight to easy patterns.

Quicksort results

Figure 4: Medians of Quicksort alternatives ordered by TOTAL Energy. T=TOTAL, p=permut, t=tielog2; green: a=ascall, g=ascglobal, l=asclocal; red: a=descall, g=descglobal, l=desclocal

Table 3: Ducksort / Quicksort2 (ratios of medians and p-values from two-sided Wilcoxon tests)

	r(%M)	r(rT)	r(pcdE)	d(pcdE)	p(rT)	p(pcdE)
TOTAL	1	0.95	0.95	-0.05	0	0
ascall	1	0.05	0.05	-0.39	0	0
descall	1	1.17	1.16	0.07	0	0
ascglobal	1	1.02	1.02	0.03	0	0
descglobal	1	1.02	1.03	0.04	0	0
asclocal	1	1.02	1.02	0.03	0	0
desclocal	1	1.02	1.03	0.03	0	0
tielog2	1	0.66	0.65	-0.25	0	0
permut	1	1.02	1.03	0.05	0	0

Table 4: Ducksort / Quicksort3 (ratios of medians and p-values from two-sided Wilcoxon tests)

	r(%M)	r(rT)	r(pcdE)	d(pcdE)	p(rT)	p(pcdE)
TOTAL	1	0.96	0.95	-0.05	0	0.0000
ascall	1	0.05	0.05	-0.36	0	0.0000
descall	1	1.20	1.20	0.08	0	0.0000
ascglobal	1	1.02	1.01	0.01	0	0.0992
descglobal	1	1.00	0.99	-0.01	0	0.0160
asclocal	1	0.97	0.97	-0.05	0	0.0000
desclocal	1	0.98	0.97	-0.05	0	0.0000
tielog2	1	1.02	0.95	-0.03	0	0.0000
permut	1	0.98	0.98	-0.04	0	0.0005

Mergesort results

Figure 5: Medians of Mergesort alternatives ordered by TOTAL Energy. T=TOTAL, p=permut, t=tielog2; green: a=ascall, g=ascglobal, l=asclocal; red: a=descall, g=descglobal, l=desclocal

Figure 6: Medians of Mergesort alternatives ordered by TOTAL eFootprint. T=TOTAL, p=permut, t=tielog2; green: a=ascall, g=ascglobal, l=asclocal; red: a=descall, g=descglobal, l=desclocal

Table 5: Squidsort2 / Knuthsort (ratios of medians and p-values from two-sided Wilcoxon tests)

	r(%M)	r(rT)	r(pcdE)	r(pcdF)	d(pcdE)	p(rT)	p(pcdE)	p(pcdF)
TOTAL	0.57	0.81	0.82	0.47	-0.22	0.0000	0.0000	0
ascall	0.57	0.38	0.38	0.22	-0.21	0.0000	0.0000	0
descall	0.57	0.15	0.17	0.10	-0.70	0.0000	0.0000	0
ascglobal	0.57	1.04	1.04	0.59	0.04	0.3595	0.4566	0
descglobal	0.57	1.00	1.01	0.58	0.01	0.1750	0.0023	0
asclocal	0.57	0.84	0.85	0.49	-0.19	0.0000	0.0000	0
desclocal	0.57	0.64	0.64	0.37	-0.66	0.0000	0.0000	0
tielog2	0.57	1.30	1.30	0.74	0.28	0.0000	0.0000	0
permut	0.57	0.87	0.88	0.50	-0.25	0.0000	0.0000	0