mergesort Questions
3
Solved
Design an algorithm that sorts n integers where there are duplicates. The total number of different numbers is k. Your algorithm should have time complexity O(n + k*log(k)). The expected time is en...
Richardo asked 1/4, 2020 at 22:51
29
Solved
I was asked this question during an interview. They're both O(nlogn) and yet most people use Quicksort instead of Mergesort. Why is that?
Tradeswoman asked 16/9, 2008 at 8:37
8
Solved
Can someone explain in English how does Non-Recursive merge sort works ?
Thanks
5
I am new to c++ and was trying develop a code for merge sort. I tested it with a sample array of size 5 but the answer put out by the code is not right. I can't figure what's going wrong. Here is m...
1
Solved
How 2-way Merge Sort are different from Merge Sort recursively?
Suppose there are 5 number to be sorted 8,9,1,6,4
In Merge Sort we divide like this
Step1: {8,9,1} {6,4}
Step2: {8,9} {1} {6} {4}...
1
I just implemented the two algorithms and I was surprised when I plotted the results! Recursive implementation is clearly faster than the iterative one.
After that, I added the insertion sort combi...
6
Solved
Java 6's Arrays.sort method uses Quicksort for arrays of primitives and merge sort for arrays of objects. I believe that most of time Quicksort is faster than merge sort and costs less memory. My e...
2
Solved
This algorithm is of mergesort, I know this may be looking weird to you but my main focus is on calculating space complexity of this algorithm.
If we look at the recurrence tree of mergesort funct...
Nepenthe asked 20/10, 2018 at 3:31
2
Solved
Which algorithm is faster when iterating through a large array: heap sort or merge sort? Why is one of these algorithms faster than the other?
5
Solved
I'm trying to understand how external merge sort algorithm works (I saw some answers for same question, but didn't find what I need). I'm reading the book "Analysis Of Algorithms" by Jeffrey McConn...
Pterosaur asked 27/12, 2013 at 14:29
0
I'm trying to understand the time complexity of a k-way merge using a heap, and although there is a plethora of literature available on it, I can't find one that breaks down the analysis such that ...
Donnetta asked 4/11, 2018 at 3:39
30
Solved
This was asked of me in an interview and this is the solution I provided:
public static int[] merge(int[] a, int[] b) {
int[] answer = new int[a.length + b.length];
int i = 0, j = 0, k = ...
1
Solved
In answers related to quicksort vs mergesort, it is commonly stated that quicksort exploits cache locality (locality of reference) better than mergesort.
As both sorts follow a divide and conquer ...
Natiha asked 30/1, 2018 at 3:34
1
Solved
The following quote is from "Comparison with other sort algorithms"
section from Wikipedia Merge Sort page
On typical modern architectures, efficient quicksort implementations
generally outper...
3
Solved
I was searching for non-recursive odd-even-merge sort algorithm and found 2 sources:
a book from Sedgewick R.
this SO question
Both algorithms are identical but false. The resulting sorting net...
Kimberliekimberlin asked 22/12, 2015 at 23:42
1
Solved
Good day SO community,
I am a CS student currently performing an experiment combining MergeSort and InsertionSort. It is understood that for a certain threshold, S, InsertionSort will have a quick...
Counterpoint asked 29/9, 2017 at 20:46
2
Solved
Why does memoization not improve the runtime of Merge Sort?
I have this question from Assignment task. But as far as I know, Merge Sort uses divide and conquer approach (no overlapping subproblems...
Sufferance asked 18/9, 2017 at 18:31
1
(disclaimer: for school)
As far as I know, recursively splitting a linked list, then sending it off to another function to merge is O(nlogn) time and O(n) space. Is it possible to do mergesort on ...
Nidify asked 22/4, 2017 at 15:1
8
Solved
I found this code online:
def merge(left, right):
result = []
i ,j = 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
resul...
4
I know that Java's Arrays.sort method uses MergeSort for sorting arrays of objects (or collections of objects) since it is stable, and Java uses QuickSort for arrays of primitives because we don't ...
4
I have written a recursive version of merge sort. It makes use of a separate merge routine:
def merge(lst1, lst2):
i = j = 0
merged = []
while i < len(lst1) and j < len(lst2):
if lst1[i]...
2
Solved
Update - Visual Studio 2022 switched to an efficient recursive implementation of merge sort where each level of recursion just divides an integer size by 2 instead of scanning lists to split them, ...
Gerrald asked 16/11, 2016 at 1:6
4
I am trying to implement a merge sort and am getting stack level too deep (SystemStackError) error when I run my code. I am not sure what the issue may be.
def merge_sort(lists)
lists if lists.co...
6
Solved
Quicksort is better than mergesort in many cases. But when might mergesort be better than quicksort?
For example, mergesort works better when all data cannot be loaded to memory at once. Are there ...
1
I was trying to do an implementation of QuickSort (with median of 3 partitioning-element and insertion sort for small arrays) and compare it to an implementation of MergeSort, but even when QuickSo...
© 2022 - 2025 — McMap. All rights reserved.