An algorithm is described which is an insertion sort producing a single linked list.The sorting method is insensitive to the key distribution.In comparison with alternative insertion sort algorithms like Shellsort algorithms, simple list insertion, and binary tree insertion, this subroutine is comparable in speed with sorting algorithms of the Shellsort type.The number of comparisons is determined by the term O(n 15).In comparison with known alternative sorting methods like quicksort and two-way merge, timing experiments with integer keys showed that the application of the algorithm is very favorable for 5 < n < 50.This may change for extremely long keys and for an ascending or a descending trend in the keys.In the first case, an algorithm which minimizes the number of comparisons (like two-way list merge) is usually faster for sufficiently large n; in the second case, the given algorithm can be favorable even for very large values of n. The Algorithm: Algorithm 505, A List Insertion Sort for Keys With Arbitrary Key Distribution.

article Free AccessArtifacts AvailableArtifacts Evaluated & Reusable Share on Algorithm 505: A List Insertion Sort for Keys with Arbitrary Key Distribution [S20] Author: Wolfgang Janko Institut fur Statistik und Mathematik, Hochschule fur Welthandel, Franz-Klein-Gasse 1, A-1190, Wien, Austria Institut fur Statistik und Mathematik, Hochschule fur Welthandel, Franz-Klein-Gasse 1, A-1190, Wien, AustriaView Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 2Issue 2June 1976 pp 204–206https://doi.org/10.1145/355681.355691Published:01 June 1976Publication History 1citation373DownloadsMetricsTotal Citations1Total Downloads373Last 12 Months12Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF