Implement sorting algorithms

[certik]

At the very least there needs to be some quick algorithm for sorting integers and reals. But I think we can implement several algorithms and the user can choose.

This will also be needed to implement #38.

[jvdp1]

Is it also an option to link to the algorithms provided by BLAS/LAPACK?

[certik]

@jvdp1 I think so. We'll need to depend on Lapack for #10 anyway.

[certik]

Here are inefficient implementations from fortran-utils: https://github.com/certik/fortran-utils/blob/b43bd24cd421509a5bc6d3b9c3eeae8ce856ed88/src/sorting.f90, the API however might be useful to get inspiration from. Here is more efficient implementation of quicksort: https://github.com/certik/hfsolver/blob/b4c50c1979fb7e468b1852b144ba756f5a51788d/src/sorting.f90#L165. I think there will be much better implementations out there, including in Lapack.

[jvdp1]

Here is a mutli-threaded one:
https://balsoftware.net/index.php/open-source/multi-thread-sort/
Not sure what is the license.

[rweed]

The following routines implement the version of quicksort outlined in Hanson's and Hopkins book and on the associated web site (http://www.siam.org/books/ot134). The publishers license is very permissive (at least as I read it). This version supports REAL32, REAL64, INT8, INT16, INT32, INT64, Character strings and arrays, and a user defined type. Unfortunately, the file tool for this page does not know anything about .f90 or .F90 file extensions. Here is the code:

Main quicksort module: type specific routines are overloaded with generic qsort interface. Sorting can be in place or return a integer permutation array leaving original array untouched. Sorting can be in either ascending or descending order.

quickSort.F90.txt

A base user class that can be extended to define user specific classes. Specifies dummy methods for relational operators needed for sorting etc, a print method and an assignment method.

userClass.F90.txt

A test program that tests sorting integers, reals, characters, and a user point class that is sorted on distance (Euclidean Norm)

testqsort.f90.txt

The point class used in test program. It is extended from the base User class

point.f90.txt

[jacobwilliams]

Here are some of mine:

• https://github.com/jacobwilliams/fortran-search-and-sort
• https://github.com/jacobwilliams/stringsort (see also here about natural sorting of strings).

[ivan-pi]

A few more:

Sorting routines in various libraries

• ACM
  • Algorithm 402 (version linked here is part of CLAWPACK)
• HSL
  • KB07
• IBM Engineering and Scientific Subroutine Library (ESSL)
  • ISORT, SSORT, and DSORT
  • ISORTX, SSORTX, and DSORTX
  • ISORTS, SSORTS, and DSORTS
• IMSL
  • SORT_REAL
  • SVRGN
  • SVRGP
  • SVIGN
  • SVIGP
  • SVRBN
  • SVRBP
  • SVIBN
  • SVIBP
• LAPACK
  • slasrt
  • dlasrt
• NAG
  • Searching and sorting
• Numerical Recipes
• ORDERPACK
• SLATEC (search for the routines ipsort, isort, spsort, ssort, dpsort, dsort, and hpsort)

Various user routines

• FlashSort (also see article in Dr.Dobbs or the Wikipedia page)
• Sorting in Fortran by Michael Rutter
• sorting programs in Fortran by Jean-Pierre Moreau
• Sorting by John Mahaffy
• FORTRAN Bubble Sort Speghetti Code by Thomas W Bennet
• MULTI-THREADED SORT by Bal Software
• quicksort by Tim Hoar
• lcpsort - Module for sorting and merging ASCII text strings by N. Shamsundar, University of Houston (a C version by the same author is provided here)
• qsort_inline by Joseph M. Krahn at FortranWiki
• Coding Fortran: a sorting module by Michael Wirth
• Parsing and Sorting with Fortran by Mike Rourke
• quicksort by @t-nissie and a modified version by @1AdAstra1
• Selection sort by C.-K. Shene
• LexicalSort by unknown author from comp.lang.fortran newsgroup
• Ancora sul sort di ‘Compilati vs. Interpretati’ – 2; blog post comparing various Fortran sort implementations (in Italian!)
• M_sort by @urbanjost
• simple_fortran_argsort by @Astrokiwi
• Bubble Sort (WikiBooks)
• Gnome sort (Rosetta Code)
• Insertion sort (Rosetta Code)

Internet forums and discussion boards

• ordering function in Fortran (comp.lang.fortran)
• Reverse quick sort in Fortran (StackExchange)
• Sorting an array from lowest to greatest FORTRAN (StackExchange)
• Fortran Bubble Sort Algorithm (StackExchange)
• Open-source version of Intel Fortran sort routines (StackExchange) provided by Rafik Zurob

Interfaces to C qsort

• Oracle
• Intel Fortran

Published works

• Books
  • Algorithms and Data Structures in F and Fortran by Robin Vowels (see chapter 1)
  • Introduction to Programming with Fortran by Ian Chivers and Jane Sleightholme (see pp. 703-732)
  • Fortran 90 & 95 Array and Pointer Techniques (eBook) by Loren P. Meissner (see chapters 2 and 3)
• Articles
  • Transferable FORTRAN Subroutine for Rapid Extended Sorting
  • Technical Note: Efficient sorting routines in FORTRAN 77

[wclodius2]

FWIW I needed a sorting procedure to sort the results of of hashing functions to estimate their tendency to produce conflicting hashes. I have implemented four sorting algorithms for sorting rank one arrays of kinds INT8, INT16, INT32, INT64, SP, DP, and QP.

1. A hybrid of quicksort using median of three for the pivot and insertion sort for the leaves. There should be no problem with distributing this algorithm with stdlib, but I have my issues with its performance on some arrays
2. A version of the introsort of David Musser used as the standard sorting for some C++ standard libraries. This is a hybrid algorithm using insertion sort for the leaves of the sort tree, quicksort by default for the main body, and heapsort if quicksort is not converging quickly. I have permission from David Musser to incorporate my version of introsort into the standard library.
3. A algorithm inspired by timsort of Tim Peters used in Python, Java, and other languages. While it claims to be timsort it is not, but has very good performance for a mergesort base sort, particularly on partly sorted data. It's sorting is not in place and stable. It requires temporary space of size N. In particular, it doesn't do the search for runs or the galloping of the original. I call this algorithm simplified timsort. I have asked the author of this algorithm, Aditya Kumar, for permission to use it.
4. A version of timsort largely a translation of the original C code to Fortran 2008. This code has at least one error discussed by N. Auger, C. Nicaud, and C. Pivoteau. Merge Strategies: from Merge Sort to TimSort. 2015. hal-01212839v2. that is fixed in my translation. I have written to two old email addresses of Tim Peters asking for permission to use my translation in stdlib, but have not heard back.

I have implemented eight sets of arrays for testing the codes, all of length 2**20.

• Random - a set of integers from 0 to 2**20 - 1 in random order.
• Identical - all integers have the same value of 10.
• Increasing - values increase uniformly from 0 to 2**20-1.
• Decreasing - values decrease uniformly from 2**20-1 to 0.
• Random-sparse - the integers are generated randomly from a set of values from 0 to 2**22-1 so duplicates are sparse.
• Random-dense - the integers are generated randomly from a set of values from 0 to 2**19-1 so duplicates are dense.
• Random-3 - the Increasing array has 3 random exchanges of individual elements.
• Random-10 - the final ten elements of the increasing array are replaced by random values.

The quicksort array sometimes exhibits quadratic behavior on the Identical, Randon-3, and Random-10 arrays so I turned off testing for this sort on these three arrays. The results of the testing are summarized by the following table. The times are averages of eight consecutive runs.

Type	Elements	Order	Method	Time (s)
Integer	1048576	Random order	QuickSort	0.14268
Integer	1048576	Increasing	QuickSort	0.04419
Integer	1048576	Decreasing	QuickSort	0.13219
Integer	1048576	Random sparse	QuickSort	0.14551
Integer	1048576	Random dense	QuickSort	0.14235
Integer	1048576	Random order	Intro_Sort	0.14291
Integer	1048576	Identical	Intro_Sort	0.14412
Integer	1048576	Increasing	Intro_Sort	0.04812
Integer	1048576	Decreasing	Intro_Sort	0.12334
Integer	1048576	Random sparse	Intro_Sort	0.14504
Integer	1048576	Random dense	Intro_Sort	0.14413
Integer	1048576	Random 3	Intro_Sort	0.10890
Integer	1048576	Random 10	Intro_Sort	0.34179
Integer	1048576	Random order	Sim_Tim_Sort	0.16737
Integer	1048576	Identical	Sim_Tim_Sort	0.06190
Integer	1048576	Increasing	Sim_Tim_Sort	0.06276
Integer	1048576	Decreasing	Sim_Tim_Sort	0.09906
Integer	1048576	Random sparse	Sim_Tim_Sort	0.16657
Integer	1048576	Random dense	Sim_Tim_Sort	0.16756
Integer	1048576	Random 3	Sim_Tim_Sort	0.06303
Integer	1048576	Random 10	Sim_Tim_Sort	0.06194
Integer	1048576	Random order	Tim_Sort	0.22234
Integer	1048576	Identical	Tim_Sort	0.00234
Integer	1048576	Increasing	Tim_Sort	0.00232
Integer	1048576	Decreasing	Tim_Sort	0.00378
Integer	1048576	Random sparse	Tim_Sort	0.20528
Integer	1048576	Random dense	Tim_Sort	0.20005
Integer	1048576	Random 3	Tim_Sort	0.00353
Integer	1048576	Random 10	Tim_Sort	0.00507

In summary,

• quicksort has good performance where it does not have quadratic behavior, and has particularly good performance on the uniformly increasing array and slightly better performance on the uniformly decreasing array.
• introsort roughly matches quicksort performance, except that it is stable where quicksort has quadratic behavior.
• Simplified timsort has about 20% slower performance on random data, but consistently very good at data with significant stretches of ordered data.
• Timsort has about 80% slower performance than introsort on random data, but extraordinary performance, essentially O(N), on data with significant stretches of ordered data.

FWIW timsort puts a lot of effort into reducing the number of comparisons of elements of the array/list at the expense of some convoluted logic. I suspect this effort is wasted on intrinsic elements and some simplification of the code would improve its performance on random data with minimal impact on its performance on largely sorted data.

[wclodius2]

I have implemented a fifth sorting routine, a translation of the Rust sorting routine to Fortran 2008. The Rust sort is also inspired by Tim Peters' Timsort algorithm, but drops the "galloping" used to rapidly find the minimum range to be sorted. It is released under the Apache License, Version 2.0 or the MIT license so the translation can be easily incorporated into the standard library. Rust sort is comparable to the simplified Tim Sort on random data, and the true Tim Sort on partially sorted data. I suggest that that a standard library sorting routines include at least two routines: one like Introsort for data that is expected to be random; and one like Rust sort for data that will often have presorted sections.

Type	Elements	Order	Method	Time (s)
Integer	1048576	Random order	QuickSort	0.14655
Integer	1048576	Increasing	QuickSort	0.04457
Integer	1048576	Decreasing	QuickSort	0.12806
Integer	1048576	Random sparse	QuickSort	0.14349
Integer	1048576	Random dense	QuickSort	0.14277
Integer	1048576	Random order	Intro_Sort	0.14568
Integer	1048576	Identical	Intro_Sort	0.14389
Integer	1048576	Increasing	Intro_Sort	0.05068
Integer	1048576	Decreasing	Intro_Sort	0.13336
Integer	1048576	Random sparse	Intro_Sort	0.15501
Integer	1048576	Random dense	Intro_Sort	0.15246
Integer	1048576	Random 3	Intro_Sort	0.09962
Integer	1048576	Random 10	Intro_Sort	0.30596
Integer	1048576	Random order	Sim_Tim_Sort	0.16140
Integer	1048576	Identical	Sim_Tim_Sort	0.06535
Integer	1048576	Increasing	Sim_Tim_Sort	0.06486
Integer	1048576	Decreasing	Sim_Tim_Sort	0.10153
Integer	1048576	Random sparse	Sim_Tim_Sort	0.15755
Integer	1048576	Random dense	Sim_Tim_Sort	0.16222
Integer	1048576	Random 3	Sim_Tim_Sort	0.06694
Integer	1048576	Random 10	Sim_Tim_Sort	0.06540
Integer	1048576	Random order	Tim_Sort	0.20426
Integer	1048576	Identical	Tim_Sort	0.00261
Integer	1048576	Increasing	Tim_Sort	0.00249
Integer	1048576	Decreasing	Tim_Sort	0.00417
Integer	1048576	Random sparse	Tim_Sort	0.20701
Integer	1048576	Random dense	Tim_Sort	0.20557
Integer	1048576	Random 3	Tim_Sort	0.00495
Integer	1048576	Random 10	Tim_Sort	0.00391
Integer	1048576	Random order	Rust_Sort	0.16567
Integer	1048576	Identical	Rust_Sort	0.00204
Integer	1048576	Increasing	Rust_Sort	0.00203
Integer	1048576	Decreasing	Rust_Sort	0.00354
Integer	1048576	Random sparse	Rust_Sort	0.16542
Integer	1048576	Random dense	Rust_Sort	0.15886
Integer	1048576	Random 3	Rust_Sort	0.00818
Integer	1048576	Random 10	Rust_Sort	0.00412

[ivan-pi]

I think having two or even three of these would be great additions to stdlib. The occurence of pre-sorted sections is typical in indexes of sparse matrices for discretized PDE problems using irregular meshes.

I just uploaded a copy of a hybrid sort (quick sort + insertion sort) by Houlsby & Sloan (both are professors of civil engineering) to a public repository: https://github.com/ivan-pi/hs-sort/. Since I could not figure out the journal licensing conditions, I have sent an email to the original author asking for permission to share the routines under a permissive license. For an array of 1048576 random ordered doubles, the timing is roughly 0.2 seconds, so on the same order as your routines.