# Questions tagged [mergesort]

The tag has no usage guidance.

49 questions
Filter by
Sorted by
Tagged with
3k 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 ...
737 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 - ...
3k 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.
397 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$ ...
517 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 ...
1k 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 ...
119 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 ...
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 ...
558 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(...
62 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 ...
889 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 ...
993 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....
121 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 ...
325 views

291 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 ...
178 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". ...
48 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: ...
28 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: ...
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 ...
203 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?
164 views

13 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 ...
390 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 ...
95 views

...
328 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. ...