Skip to main content

Questions tagged [mergesort]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
2 answers
49 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?
barnyard9's user avatar
  • 133
1 vote
1 answer
98 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 ...
vhd's user avatar
  • 45
0 votes
0 answers
27 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 ...
chenzhongpu's user avatar
2 votes
3 answers
179 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 ...
R. Javid's user avatar
  • 131
0 votes
2 answers
77 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:]$ ...
WalaWizon's user avatar
0 votes
1 answer
168 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 ...
Rohit Pandey's user avatar
1 vote
1 answer
85 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 ...
The Pointer's user avatar
0 votes
1 answer
32 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 ...
The Pointer's user avatar
0 votes
1 answer
153 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?
Anmol Gupta's user avatar
0 votes
0 answers
72 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 ...
Xenotion's user avatar
1 vote
0 answers
151 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 ...
PwNzDust's user avatar
  • 111
2 votes
3 answers
121 views

Number of comparisons for mergesort

In their book An introduction to the Analysis of Algorithms, Flajolet and Sedgewick analyze the number of compares performed by Mergesort along the following lines. They denote by $C_N$ the number of ...
Boz Steinkalt's user avatar
1 vote
2 answers
545 views

Sorting an array with x sorted subarrays

I have been given two True/False questions regarding sorting an array. The questions are as following - Question A Given an array A with 3n keys that contains three equal parts A[1,n], A[n+1,2n] and ...
MathCurious's user avatar
0 votes
3 answers
208 views

Runtime of sorting algorithms given a particular input

say that we have {2,3,5,4,6} as input that we want to sort in ascending order. Then, we know that we can use any of the sorting algorithms: bubble, insertion, selection, quick, merge, heap or counting....
Edmond Craig's user avatar
1 vote
2 answers
1k views

How does size of list in merge-sort, quick-sort, insertion-sort, matter?

We have been taught that: Insertion-sort will best work if we have a small list. Quick-sort will best work if we have a long list. Merge-sort will best work if we have a huge list. It is not ...
amkyp's user avatar
  • 27
0 votes
2 answers
122 views

How to known which algorithm is the best for what situation, when sorting numbers?

Is there some kind of "universal list" of performance of different algorithms in different situations? I have different databases that save user input (numbers). However some of these sets ...
linker's user avatar
  • 111
1 vote
0 answers
63 views

Merge Sort sentinel: What if your array contains Integer.MAX_VALUE?

I'm just getting my head round Merge Sort, and I was wondering whether the use of the sentinel value was considered good practice in the real world, or mostly an algorithmic conceit? I get that it ...
robhogg's user avatar
  • 11
0 votes
0 answers
64 views

External Sorting - Calculate passes with different number of disks

Let suppose that we have a file with n = 10^6 records. The block size is B = 10 records and we have available main memory m = 20 blocks. (Sorting with MergeSort) a) If we have 1 disk find minimum ...
Maria Zak's user avatar
1 vote
1 answer
1k views

Bottom-up Mergesort vs Natural Merge Sort

I ran into natural mergesort in this Wikipedia page: https://en.wikipedia.org/wiki/Merge_sort#Natural_merge_sort However, I can't find much information regarding: The algorithm(s) to achieve natural ...
zemageht's user avatar
1 vote
1 answer
446 views

Worst case running time of lexicographical sorting of a list of n strings each of length n using merge sort

This same question has been asked here so many times by several people. This is a problem which was asked in an entrance exam. And I am having difficulties in digesting the correct answer of this ...
rsonx's user avatar
  • 281
1 vote
1 answer
100 views

Runtime of Divide and Conquer Flavored Bogo Sort

Here we propose a way to reduce Bogo Sort's runtime from factorial to exponential using a divide and conquer approach. This is something we have likely all pondered on extensively. https://en....
Matthaeus Gaius Caesar's user avatar
1 vote
1 answer
25 views

How can divide by 2 blocksize bubblesort followed by a final mergesort be optimized in a particular environment?

I am wondering if we had a large array to sort (let's say 1,048,576 random integers), chosen because it is a perfect power of 2, if we can just keep dividing those blocks into smaller and smaller half ...
David James's user avatar
1 vote
1 answer
1k views

Quick Sort vs Radix Sort

In an coding exam, I was once asked this question: Assuming that you are only sorting Integers in ascending order, which algorithm do you use when you want to prioritize speed the most, but you ...
Richard Peterson's user avatar
1 vote
2 answers
1k views

Why does MergeSort have O(n) space complexity if it splits the array log(n) times?

I know this is a common algorithm with plenty of analysis, but when I searched for an answer the only one I found was "Merge Sorting has O(n) auxiliary space because it copies the array into L and R". ...
NaT3z's user avatar
  • 113
5 votes
1 answer
1k views

How can merging two sorted arrays of N items require at least 2N - 1 comparisons in every case?

The HW question, on page 362 of Data Structures and Algorithms in C++: Fourth Editionby Mark Allen Weiss, reads as follows: Prove that merging two sorted arrays of N items requires at least 2 * N - ...
Darien Springer's user avatar
1 vote
0 answers
548 views

Time complexity of a hybrid merge and selection sort algorithm

I'm trying to analyse the time and space complexity of the following algorithm, which is essentially a hybrid of a merge and selection sort. The algorithm is defined as follows: ...
electro7912's user avatar
0 votes
0 answers
599 views

Job Scheduling with deadline with $nlogn$ algorithm

We know that there is a Greedy algorithm for scheduling of $n$ jobs which each job has its own deadline and profit. In greedy algorithm, we sort the set by their profit descendant, And if a job can ...
Mohammad's user avatar
1 vote
1 answer
445 views

Space Complexity of Bottom-Up Merge Sort

What is the space complexity of Bottom-up merge sort? It uses iteration rather than recursion so it will not use stack. But will an auxiliary array be used for the merge operation? Please explain. ...
Abhipsa Mishra's user avatar
1 vote
2 answers
1k views

number of permutation with k inversions

We are given two numbers N and K. N <= 10^9. K<=min{1000,(N*(N-1))/2} We need to find numbers of permutations of ( 1 to N ) such that inversions are exactly K. If N was <= 10^3. It would ...
user avatar
1 vote
0 answers
29 views

Is there a name for the technique used in the "merge" part of MergeSort?

MergeSort has two parts, "divide" and "merge" (arguably three if you include "recurse" as its own part in the middle). I'm interested in the "merge" part, which tends to look like this: ...
Green Cloak Guy's user avatar
2 votes
2 answers
673 views

Merge Sort Confusion - Initial Phase Missing?

Below is the solution to a merge sort exercise - "Use a merge sort to sort the list". I'm confused because I thought that there needed to be an initial phase of breaking the list in to sub-lists, yet ...
Robin Andrews's user avatar
3 votes
1 answer
826 views

Worst Case Space Complexity of Merge Sort and Bubble Sort

I understand that the worst space complexity of Bubble Sort is constant O(1), since all the space we need is the array where the elements were stored. But why is Merge Sort's worst space complexity O(...
alyssaeliyah's user avatar
3 votes
3 answers
75 views

Why is subarray $A[p..k-1]$ empty when $k=p$?

I'm working through a proof of correctness for merge sort. I'm given a loop invariant for a for loop, which makes reference to a subarray $A[p..k-1]$. During the initialization step of the ...
Data's user avatar
  • 215
5 votes
2 answers
929 views

Complexity of Merge Sort that splits in a random position

I got a question that I don't fully understand: Given a new algorithm to merge sort (AKA mergesort2) that instead of splitting the list in the middle it splits the list in a random number between $1$ ...
EladAskenazi's user avatar
5 votes
1 answer
284 views

Merge sort in place

I don't quite understand why in-place sort merge sort isn't preferred over not-in place? Is it because theoretically in place merge sort is better because of its memory complexity tradeoff, but in ...
neet's user avatar
  • 51
1 vote
1 answer
50 views

Recurrence Relation Mergesort

I was reading Algorithms 4th Edition by Sedgewick et al. and I found this statement when discussing about the analysis of mergesort: The number of compares is at most n and no less than $\lfloor n/...
S. Sharma's user avatar
  • 145
2 votes
1 answer
892 views

Merge sort: sorting and merging complexity $\Theta(n)$

So this is the Master theorem for Merge Sort: $$ T(n) = 2T(n/2) + \Theta(n). $$ I am not able to understand why is the time complexity for sorting and merging $\Theta(n)$. Is sorting $O(1)$ and ...
Arjun Hegde's user avatar
0 votes
2 answers
1k views

Merge sort and quicksort recursion tree depth

1) I need to determine recursion tree depth for strings composed of 10, 100 and 1000 elements when using merge sort. For the 10 elements one/I can do it on a paper, just drawing tree, but what about ...
Karol's user avatar
  • 101
1 vote
1 answer
86 views

MergeSort k arbitrary words in linear time

Given $k$ arbitrary words, such as $\{\text{"fjqke"}, \text{"gbqig"}, \text{"a"}\}$, is there a way to mergesort these words in linear time so that the final output would be "abefgggijkq"? I tried to ...
Brian Ko's user avatar
  • 113
2 votes
1 answer
163 views

Compute the general time complexity of a merge sort algorithm with specified complexity of the merge process

The problem was from an exam, I spent much time wrapping my head up around this kind of problems, so I decided to ask for help ;( Problem: We implement a merge sort algorithm to sort $n$ items. The ...
OOD Waterball's user avatar
0 votes
1 answer
980 views

Merge sort mxn matrix

The question is as follows: I am new to this, and I do not understand how to apply divide and conquer to a matrix, the algorithm that I have come up with is as follows (I am not sure if I am correct) ...
shakeel osmani's user avatar
2 votes
1 answer
3k views

Merging $k$ sorted lists in $O(n\log k)$ time

This question is based on a solution of Laura Toma to a question from CLRS (#6 on the sheet). Question: Give an $O(n\lg k)$-time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is ...
Hello's user avatar
  • 169
1 vote
1 answer
618 views

Counting Inversions with merge-sort

I'm doing this course: Engineering: Algorithms1 - SELF PACED Algorithms: Design and Analysis, on Stanford's website. And the first assignment asked us to count the inversions in an array. The idea ...
DTek's user avatar
  • 113
5 votes
1 answer
618 views

Merge sort worst case running time for lexicographical sorting?

A list of n strings each of length n is being sorted in lexicographical order using the merge sort algorithm. Since we have to take care of comparison of each character in the strings so the merge ...
Navjot Singh's user avatar
  • 1,215
0 votes
1 answer
236 views

What is the time complexity of MergeSort without its penultimate merge?

As in, with the two final sublists which are sorted arrays, let's say just for this example (yes it is no longer fully MergeSort but I am interested in the time complexity only), that we finish with a ...
user avatar
2 votes
1 answer
362 views

Proving time-complexity analysis for merge-sort-like algorihtm

I have this algorithm, which is exactly like merge-sort, but instead of halving the array each recursion, it actually splits it into $1/4$ and $3/4$ parts. Other then that, it does exactly the same ...
0rka's user avatar
  • 121
0 votes
1 answer
26 views

Merge Sort meaning of a bit part of code

I am studying this part for a merge sort implementation: ...
kevin parra's user avatar
0 votes
0 answers
114 views

How to find Time complexity of merge sort with parameter?

...
J.Doe's user avatar
  • 9
2 votes
1 answer
548 views

Exact Analysis of the Merge Sort

When doing the "inexact" analysis of the Merge Sort, the literature that I have seen usually consider that the input is an array with a even quantity of numbers and the recurrence relation is: $T(n) =...
LionsWrath's user avatar
2 votes
1 answer
3k views

To find median of $k$ sorted arrays of $n$ elements each in less than $O(nk\log k)$

How do I efficiently find the median of $k$ sorted arrays each of length $n$? Note that the total number of elements will be $nk$. I know it can be done in $O(nk \log k)$ time using merge technique. ...
shiwang's user avatar
  • 481