All Questions
8
questions
0
votes
0
answers
303
views
Prove that MergeSort is stable for any input size n ∈ N using induction on n.
In terms of a list of objects with two separate fields, suppose a stable sort would order the list in increasing order. However, if two elements have the same number, then they'll appear in the same ...
1
vote
1
answer
601
views
How do I prove by using induction on k, that MergeSort uses $n(\log_2(n)+1)=2^k(k+1)$ comparisons?
I have been asked this question in an assignment for my exam.
The assignment question is: "Assume that Merge uses (exactly) $a+b-1$ comparisons to combine two lists with a and b elements. ...
- 13
1
vote
2
answers
7k
views
How many comparisons does the insertion sort use to sort the lists in question
I have two lists to sort using insertion sort:
How many comparisons does the insertion sort use to sort the list
$n, n − 1, . . . , 2, 1$?
How many comparisons does the insertion sort use to sort ...
- 1,189
1
vote
1
answer
278
views
Randomized Quick Sort and Partition Probability?
We know about Quick Sort and Randomized Version and Partition. I ran into a Fact when I read my notes.
Let $0 < a < 0.5$ be some constant. We have an $n$-element array as input. Randomized ...
2
votes
2
answers
11k
views
Can anyone explain the average case in insertion sort?
I am not sure if this question is off topic or not but a question like this has been asked on this site before - Insertion sort proof
Here is an example of insertion sort running a on a set of data
...
- 1,884
3
votes
2
answers
554
views
Application of Mergesort
We have $8$ players and we want to sort them in $24$ hours.
There is one stadium. Each game lasts one hour.
In how many hours can we sort them??
I thought that we could it as followed:
$$\boxed{...
- 14k
0
votes
1
answer
452
views
Merge two sets, list and tree
We are given two sets $S_1$ and $S_2$.
We consider that $S_1$ is implemented, using a sorted list, and $S_2$ is implemented, using a pre-order sorted tree.
I have to write a pseudocode, that ...
- 7,879
2
votes
2
answers
202
views
Could graph theory aid in the understanding of comparison sorting algorithms?
I am interested in computing the exact number of comparisons that are needed to sort a list. See this wikipedia article.
Up to $n=15$, we know how many comparisons between elements one must make to ...
- 7,148