Questions tagged [mergesort]
The mergesort tag has no summary.
67 questions
0
votes
1
answer
102
views
-1
votes
4
answers
253
views
Space Complexity of Merge Sort
What is the specific space complexity of the Merge Sort algorithm, as partially implemented below?
...
- 13
0
votes
3
answers
2k
views
O(nloglogn) Sorting Algorithm?
I have come up with an sorting algorithm that looks like $O(n \log \log n)$. Could anyone help to find if it is already commonly known or worth anything?
The time complexity seems to be: $T(n) = \...
5
votes
3
answers
2k
views
Is this a potentially more intuitive approach to MergeSort?
I have read at least one other post (perhaps not on this stackexchange) that asks essentially: Why do we have to break up the array into successively smaller arrays until we finally reach the bottom (...
- 151
0
votes
2
answers
176
views
If mergesort takes 30 sec to sort 64 elements in worst case, how many elements can be sorted at worst case by using it in 6 minutes?
To sort 64 elements
Time required is $n*log_2{n}$ units
The equivalent posteriori time is 30 sec.
In 6 minutes
I get 768 elements sorted.
But the answer is not 768 and is instead 512, I wonder why?
- 289
1
vote
1
answer
205
views
Restore the original array after merge Sort based on it's steps
i'm trying to write an algorithm to reconstruct the original array from the sorted one. considering input value is a string of 1s and 2s which 1 means in merging part of merge sort, element from left ...
- 67
0
votes
0
answers
44
views
Recurrence for C(N+1) - C(N) of mergesort
I am reading "An Introduction to the Analysis of Algorithms" by Robert Sedgewick and Kevin Wayne. In this book, Exercise 1.4 asks to develop a recurrence for $C_{N+1} - C_{N}$ and use it to ...
- 101
2
votes
3
answers
310
views
Partition an array in two groups while keeping the relative order within both groups
I came across the following problem in the book "Elements of Programming Interviews in Python".
Given an array A of n objects with Boolean-valued keys, reorder the array so that objects ...
- 173
0
votes
2
answers
123
views
merging logn + 1 sorted subarrays
given array A of size $n$ which is made of $logn + 1$ sub arrays which are sorted,
I need to sort ASAP.
example of array : $A[500,501,3,8,100,1,2,9]$ as you can see, sub arrays are :$[1:2][3:5][6:]$
...
- 11
0
votes
1
answer
264
views
Why does merge sort work for any $n$, but the basic FFT algorithm only for powers of $2$?
Merge sort and FFT are both divide and conquer algorithms that split the input in two repeatedly. While merge sort can be applied to any $n$, the FFT algorithm given in CLRS (section 30.2, third ...
- 397
1
vote
1
answer
140
views
Divide-and-Conquer Algorithms: What exactly is $a$ and $b$ here?
Chapter 2.3.2 Analysing divide-and-conquer algorithms of Introduction to Algorithms, fourth edition, by CLRS, says the following:
A recurrence for the running time of a divide-and-conquer algorithm ...
- 227
0
votes
1
answer
66
views
Applying merge sort: Would the value in the box with the red cross be $71$? Does it matter whether we start at the bottom-left or bottom-right?
I have the following diagram showing a case of merge sort:
I am trying to find the value that would be in the box with the red cross when applying merge sort in ascending order.
It seems to me that ...
- 227
0
votes
1
answer
228
views
In merge sort, what will be the time complexity if in each recursion, we break the array in two parts of size 1/4 and 3/4 respectively?
Let's say number of elements are a power of 4. Now if we break the array in parts of 1/4 and 3/4, how do we calculate the time complexity in this case?
- 101
0
votes
0
answers
114
views
How will changing the splitting point in merge sort affect the algorithm and its time complexity
Everyone knows that merge sort will continuously divide the array into halves until they are small enough to (like 2 elements per block or so) be able to be sorted quickly, hence its time complexity ...
- 1
1
vote
0
answers
200
views
Showing that for all positive integers m and n there are sorted lists with m elements and n elements such that m+n-1 comparisons are needed
I was trying to solve a discrete math question regarding the comparison needed by a merge-sort algorithm. I wanted to ask if there were a more formal way to put organize my reasoning for this problem ...
- 111