Recursive merge sort with erroneous comparisons

DOI10.1016/j.dam.2011.05.010zbMath1228.68023OpenAlexW2073438146MaRDI QIDQ642963

Petros Hadjicostas, K. B. Lakshmanan

Publication date: 27 October 2011

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.05.010

zbMATH Keywords

errorssortinganalysis of algorithmscomparisonsrunsinversionsmeasures of disarrayrecursive merge sort

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Related Items (6)

Optimal Dislocation with Persistent Errors in Subquadratic Time ⋮ Distribution of the sum-of-digits function of random integers: a survey ⋮ Optimal dislocation with persistent errors in subquadratic time ⋮ Unnamed Item ⋮ Longest increasing subsequence under persistent comparison errors ⋮ Sorting with Recurrent Comparison Errors

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Designing reliable algorithms in unreliable memories
• Sorting and searching in faulty memories
• The price of resiliency: a case study on sorting with memory faults
• Optimal resilient sorting and searching in the presence of memory faults
• On sorting in the presence of erroneous information
• Right invariant metrics and measures of presortedness
• Braking the \(\Theta(n\log^ 2 n)\) barrier for sorting with faults
• Measures of Presortedness and Optimal Sorting Algorithms
• On Fault-Tolerant Networks for Sorting
• Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks with Destructive Faults
• Quicksort with Unreliable Comparisons: A Probabilistic Analysis
• Searching games with errors -- fifty years of coping with liars

This page was built for publication: Recursive merge sort with erroneous comparisons