Questions tagged [mergesort]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
16 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. ...
0
votes
1answer
229 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 ...
0
votes
0answers
12 views

What is the work complexity for optimal merge using partitioning of sorted array of size n and p processors with segments of size n/p?

Using optimal method to find rank, we can partition a sorted array(size n) in segments of size n/p using p processors. The, we can find the rank of an element by placing a processor at the start and ...
0
votes
2answers
97 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 ...
4
votes
1answer
104 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 ...
1
vote
0answers
27 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: ...
2
votes
2answers
49 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 ...
2
votes
1answer
160 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(...
3
votes
3answers
58 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 ...
4
votes
2answers
188 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$ ...
1
vote
1answer
30 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/...
0
votes
1answer
90 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 ...
0
votes
1answer
21 views

Merge Sort meaning of a bit part of code

I am studying this part for a merge sort implementation: ...
1
vote
1answer
56 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 ...
2
votes
1answer
48 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 ...
0
votes
1answer
300 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) ...
2
votes
1answer
816 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 ...
1
vote
1answer
248 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 ...
5
votes
1answer
479 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 ...
0
votes
1answer
152 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 ...
2
votes
1answer
122 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 ...
0
votes
0answers
81 views
2
votes
1answer
219 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) =...
1
vote
2answers
237 views

Confusion over the complexity of parameter passing in merge sort

I'm working through CLRS on problem 4-2, which says the following: Throughout this book, we assume that parameter passing during procedure calls takes constant time, even if an $N$-element array is ...
1
vote
0answers
1k views

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

How to find median of k sorted arrays each of length n? Note that total elements would be n*k. I know it can be done in O(n*k*log(k)) using merge technique. I am looking for a better time efficient ...
3
votes
1answer
692 views

Radix, merge, counting sort and when to use

Okay can't figure this out. I want to make sure I understand it. There are n random keys each being float numbers with p decimal places. So, for example, 123.456, 343.645, 234.543, 863.238, 956....
1
vote
1answer
112 views

Sort huge file algoritm [closed]

What algorithm should be used here to solve this problem efficiently? One file stores 5 year log of user IDs & their website visit dates in random order. There were around 1,000,000 users on the ...
1
vote
0answers
192 views

Scenarios where merge sort is preferred over quick sort

As merge sort and quicksort both have the same average time complexity of $O(n \log(n))$. In which scenarios would merge sort be preferred over quicksort when sorting data?
4
votes
1answer
2k views

Is Timsort more efficient than merge sort and why?

I was just wondering, I think merge sort is more efficient but not sure if that is true. I know it's to do with the complexities but am still struggling to understand.
1
vote
1answer
148 views

The constant in the merge sort recurrence

Assuming that the worst case running time of merge sort can be described with this recurrence: $\ T(n) = \begin{cases} \theta(1) & \text{if }n = 1\\ 2T(\frac{n}{2}) + \theta(n) & \...
2
votes
2answers
2k views

Expected number of comparisons in a merge step?

I know that merging two sorted arrays takes worst case n comparisons. However, there will often be cases where one array is depleted before the other, letting us just append the remainder of one array ...
13
votes
2answers
2k views

Can the “divide” step in a merge sort be avoided?

So merge sort is a divide and conquer algorithm. While I was looking at the above diagram, I was thinking if it was possible to basically bypass all the divide steps. If you iterated over the ...
4
votes
2answers
3k views

Why top down merge sort is popular for learning, while most libraries use bottom up?

Most libraries use some variation of bottom up merge sort, but top down merge sort seems to dominate web sites and forums. Assume reasonably optimized implementations, where a single working array is ...
0
votes
0answers
284 views

Determining the cost of multi phase multiway merge sort

Let's say I have a disk with an average seek time of 10ms, an average rotational latency of 5ms and a transfer time of 1ms for a 4kb block and the cost of reading the block is the sum of these values. ...
2
votes
2answers
911 views

Creating a temp array vs passing one in Mergesort

In my CS class, we've discussed two ways of dealing with the temporary array required for the merging phase of mergesort. One of them is to pass a full-size temporary array as a parameter, e.g. merge(...
3
votes
2answers
702 views

Insertion sort vs Merge sort - memory access

I am a computer science sophomore doing a data structures and algorithms course. My professor said that insertion sort requires random access, while merge sort does not. According to him, the ...
5
votes
0answers
915 views

Is this in-place merge algorithm efficient or not?

I have trouble analyzing the characteristics of this algorithm that merges two adjacent sorted lists. Basically it looks at some number of the tail of the first list, and the same number of head ...