Chairs
©Sourendu Gupta

List all links on this page

Contact me

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.

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
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.

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