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]

Mergesort (A,p,r)  //start with p = 1 and r = A.length
  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
      A[m] = R[j]
      j = j + 1
  • $\begingroup$ 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. $\endgroup$ – preetsaimutneja Jul 2 '14 at 12:56
  • $\begingroup$ @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. $\endgroup$ – MNRC Jul 2 '14 at 13:03
  • $\begingroup$ 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)$ $\endgroup$ – lPlant Jul 2 '14 at 13:11
  • $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ This is a good solution to the problem, but not an answer to the question as you don't use Mergesort. $\endgroup$ – 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 !

  • 2
    $\begingroup$ Better to provide more details and justifications. $\endgroup$ – hengxin Jan 27 '16 at 7:40
  • 1
    $\begingroup$ What about the recursive calls? $\endgroup$ – Raphael Jan 27 '16 at 8:04
  • $\begingroup$ @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. $\endgroup$ – Parag Gupta Jan 27 '16 at 18:41
  • $\begingroup$ 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. $\endgroup$ – Parag Gupta Jan 28 '16 at 4:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.