Asymptotically fastest sorting algorithm for almost sorted arrays

MaRDI QIDQ4993799zbMATH OpenFDO

Authors Stefan Gerdjikov

Publication date 16 June 2021

Full work available at URL https://www.fmi.uni-sofia.bg/en/node/6731

zbMATH Keywords

increasing subsequencespatience sorting algorithmworst-case optimality

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms (68W40)

Recommendations

• Sorting shuffled monotone sequences
• In-place sorting
• Fast stable in-place sorting with \(O(n)\) data moves
• Sorting with minimum data movement
• In-place sorting with fewer moves

Cites work

• A decomposition theorem for partially ordered sets
• Combinatorics of patience sorting piles
• scientific article; zbMATH DE number 3989345 (Why is no real title available?)
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
• On computing the length of longest increasing subsequences

Cited in

(2)

• Zig-zag sort
• LATIN 2004: Theoretical Informatics

This page was built for publication: Asymptotically fastest sorting algorithm for almost sorted arrays

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993799)