Recursive merge sort with erroneous comparisons

DOI10.1016/J.DAM.2011.05.010zbMATH Open1228.68023OpenAlexW2073438146MaRDI QIDQ642963FDOQ642963

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Measures of Presortedness and Optimal Sorting Algorithms
• Searching games with errors -- fifty years of coping with liars
• Braking the \(\Theta(n\log^ 2 n)\) barrier for sorting with faults
• On Fault-Tolerant Networks for Sorting
• Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks with Destructive Faults
• 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
• Generating nearly sorted sequences -- the use of measures of disorder
• Measures of disorder and straight insertion sort with erroneous comparisons
• Quicksort with Unreliable Comparisons: A Probabilistic Analysis

Cited In (7)

• 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
• Longest increasing subsequence under persistent comparison errors
• Sorting with Recurrent Comparison Errors
• Making bubblesort recursive
• Title not available (Why is that?)

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Worst-Case Efficient Sorting with QuickMergesort 👍 👎
• Efficient unbalanced merge-sort 👍 👎
• Bottom-up mergesort -- A detailed analysis 👍 👎
• The heap-mergesort 👍 👎
• Recurring Comparison Faults: Sorting and Finding the Minimum 👍 👎
• Correction: Parallel Merge Sort 👍 👎
• Sorting with Recurrent Comparison Errors 👍 👎

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)