# How do you return the k smallest elements of an array using Mergesort?

I'd like to create a modified mergesort algorithm to return the k smallest elements of an array. The mergesort algorithm below sorts an unordered array of size n. How do I modify the algorithm so that it returns the k smallest elements of the array?

A = [1...n]

if p < r
q = floor((p + r)/2)
Mergesort (A,p,q)
Mergesort (A,q + 1,r)
Merge-Sort (A,p,q,r)

Merge-Sort (A,p,q,r)
n1 = q - p + 1
n2 = r - q
Let L[1,2,..,n1+1] and R[1,2,..,n2+1] be new arrays
for i = 1 to n1
L[i] = A[p + i - 1]
for j = 1 to n2
R[j] = A[q + j]
L[n1 + 1] = (an infinitely big number)
R[n2 + 1] = (an infinitely big number)
i = 1
j = 1
for m = p to r
if L[i] <= R[j]
A[m] = L[i]
i = i + 1
else
A[m] = R[j]
j = j + 1

• What is the intended time complexity ? because merge-sort is $O(nlogn)$ where $n$ is the number of elements, you can simply sort and take the kth element. – preetsaimutneja Jul 2 '14 at 12:56
• @sai_preet I think time complexity should be no slower than O(n logn). Not sure if I misunderstood, but I need to take the the k smallest elements, no the kth one. – MNRC Jul 2 '14 at 13:03
• It doesn't change the time complexity at all, since $n<k$ it will take $O(n log n)$ to sort, then $O(K)$ to get the smallest one, which is at worst $O(n)$, so after the sort the whole run time is still just $O(nlogn)$ – lPlant Jul 2 '14 at 13:11
• Please edit your question to remove the code. This site is about concepts, algorithms, principles, etc. behind computer science, not about code or implementation. As far as I can tell, you just copy-pasted pseudocode for standard mergesort into your question. That is not helpful and adds no value. – D.W. Jul 2 '14 at 19:12

One way to do this would be a select, partition then sort technique. First you use the Median of medians algorithm to find the $k$th smallest element, this takes $O(n)$ time.

After that has been found you partition your list, partition using this $k$th element as a pivot. This takes $O(n)$ time.

Now if you want the result sorted you can use mergesort on these $k$ elements, taking $O(k\log k)$ time, at worst case if $n=k$ then this whole process runs in $O(n\log n)$ time, the expected case is less but depends on $k$.

• This is a good solution to the problem, but not an answer to the question as you don't use Mergesort. – Raphael Jan 27 '16 at 8:06

What if in Merge Step you only merge first K elements ? That way you should have O(k*logN) time complexity !

• Better to provide more details and justifications. – hengxin Jan 27 '16 at 7:40
• What about the recursive calls? – Raphael Jan 27 '16 at 8:04
• @Raphael : Recursive call we go to a maximum level of log N (as it goes in normal mergesort ) but the merge step will always just merge the first K elements, which would give you the smallest K elements at the end of the algorithm. – Parag Gupta Jan 27 '16 at 18:41
• So, you need to go to log N level to sort two adjacent elements. But, in Merge Step, you have two sorted array of same size say m. Now, you only need to merge until you get first K elements as rest of the elements of the two arrays will definitely not be in the answer. – Parag Gupta Jan 28 '16 at 4:04