Recursive merge sort with erroneous comparisons

DOI10.1016/J.DAM.2011.05.010MaRDI QIDQ642963zbMATH OpenOpenAlexFDO

Authors Petros Hadjicostas, K. 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

errorsanalysis of algorithmssortingrunsinversionscomparisonsmeasures of disarrayrecursive merge sort

Mathematics Subject Classification ID

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

Recommendations

• Sorting with Recurrent Comparison Errors
• scientific article; zbMATH DE number 2147931
• Worst-case efficient sorting with QuickMergesort
• Correction: Parallel Merge Sort
• scientific article; zbMATH DE number 2089999
• Efficient unbalanced merge-sort
• The heap-mergesort
• Recurring comparison faults: sorting and finding the minimum
• Bottom-up mergesort -- A detailed analysis

Cites work

• scientific article; zbMATH DE number 46153 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 2147931 (Why is no real title available?)
• scientific article; zbMATH DE number 2089999 (Why is no real title available?)
• scientific article; zbMATH DE number 3049708 (Why is no real title available?)
• Braking the \(\Theta(n\log^ 2 n)\) barrier for sorting with faults
• Designing reliable algorithms in unreliable memories
• Generating nearly sorted sequences -- the use of measures of disorder
• Measures of Presortedness and Optimal Sorting Algorithms
• Measures of disorder and straight insertion sort with erroneous comparisons
• On Fault-Tolerant Networks for Sorting
• On sorting in the presence of erroneous information
• Optimal resilient sorting and searching in the presence of memory faults
• Quicksort with Unreliable Comparisons: A Probabilistic Analysis
• Right invariant metrics and measures of presortedness
• Searching games with errors -- fifty years of coping with liars
• Sorting and searching in faulty memories
• The price of resiliency: a case study on sorting with memory faults
• Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks with Destructive Faults

Cited in

(8)

• Making bubblesort recursive
• Optimal dislocation with persistent errors in subquadratic time
• Optimal sorting with persistent comparison errors
• Measures of disorder and straight insertion sort with erroneous comparisons
• Sorting with Recurrent Comparison Errors
• scientific article; zbMATH DE number 2147931 (Why is no real title available?)
• Distribution of the sum-of-digits function of random integers: a survey
• Optimal dislocation with persistent errors in subquadratic time

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

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