Codes

Building Blocks

Mergesort

Since implementation of bootstrap needs a sorting routine, I wrote a rough and ready f90 code for mergesort (this uses a bubble sort for small subarrays of length less than magic). As you know, Mergesort has complexity O(n log n). A code for checking whether a list is sorted has complexity O(n). This version of the code uses an external routine for swapping two elements of the array; inlining this does not change execution times appreciably.

Mergesort run times (in CPU seconds) on a 3 GHz Intel Core 2 quad processor Q9650 with the ifort compiler options -ip -O2. For each vector length N, columns show different values of magic. The optimum is magic≅8.

N	(16)	(8)	(6)	(5)	(4)	(3)
100		0.068	0.064	0.068	0.068
1000	0.900	0.876	0.884	0.908	0.932
10000	11.080	11.060	11.228	11.380	11.784	12.252
100000	136.100	132.492	135.540	137.332	139.928	144.973

---

© Sourendu Gupta. Last modified on 12 Nov, 2024 Code linked from this page is supplied without warranty under the GNU General Public License.