Articles of sorting

Find 3rd largest number out of 7 under at most 11 comparisons

I know similar problem like “sort 5 numbers in 7 comparisons”. I know no general algorithms exist. Do I just enlist all possible game trees?

Sort vectors according to their distance between them

I have a collection of vectors, let`s say $n$ vectors. I am trying to find an easy way to SORT these vectors in that way that after sorting of vectors $(V_1,V_2,…,V_n)$ the first vector $V_1$ and the last vector $V_n$ will be two furthest vectors. Next $V_{n-1}$ will be the second farthest vector from the […]

Merge Sort time complexity analysis

How can I prove that $T(n) = 2T(n/2) + n$ is $O(n \log n)$ ?

Why is sorting pancakes NP hard?

An article posted yesterday (http://www.i-programmer.info/news/112-theory/3280-pancake-flipping-is-hard-np-hard.html) references a new study released on Arxiv (http://arxiv.org/abs/1111.0434v1) with the following summary: Pancake Flipping is the problem of sorting a stack of pancakes of different sizes (that is, a permutation), when the only allowed operation is to insert a spatula anywhere in the stack and to flip the pancakes above […]

Worst case analysis of MAX-HEAPIFY procedure .

From CLRS book for MAX-HEAPIFY procedure : The children’s subtrees each have size at most 2n/3 – the worst case occurs when the last row of the tree is exactly half full I fail to see this intuition for the worst case scenario . Can some one explain possibly with a diagram . Thanks . […]

Linear algebra to find EV of sort algorithm

I am having a hard time figuring out how to use Markov chains to address a sorting method. It is for a PE problem (i.e. problems done for fun), if anyone’s curious. I do not want spoilers but just some guidance on the right track as to the method. I understand what Markov chains are […]