0
$\begingroup$
public static void MergeSort(int[] a, int p) {
  MergeSort(a, 0, a.length - 1, p);
}
private static void MergeSort(int[] a, int start, int end, int p) {
  if (end - start > 0) {
    int middle = (start + end) / 2;
    MergeSort(a, start, middle, p);
    MergeSort(a, middle + 1, end, p);
    Merge(a, start, middle, end, p);
  }
}
private static void Merge(int[] a, int start, int middle, int end, int p) {
  int[] b = new int[Math.min(end - start + 1, p)];
  int i = start, j = middle + 1, k = 0;
  while (i <= middle && j <= end && k < p)
    if (a[i] < a[j]) b[k++] = a[i++];
    else b[k++] = a[j++];
  while (i < middle && k < p)
    b[k++] = a[i++];
  while (j <= end && k < p)
    b[k++] = a[j++];
  for (k = 0; k < b.length; k++)
    a[start + k] = b[k];
}

I need to Find Time complexity of MergeSort ?

the time complexity of Merge is O(min (p,n)) ,so the time complexity of MergeSort is O(min (p,n)log(min (p,n)))

is this correct and if not how to find the correct time complexity?

and if I want to prove that MergeSort return Array that containing the first p elements that are the smallest and they are sorting ?

thanks.

$\endgroup$
  • $\begingroup$ "the time complexity of Merge is O(min (p,n)) ,so the time complexity of MergeSort is O(min (p,n)log(min (p,n)))" -- what's your reasoning for that? $\endgroup$ – Raphael May 6 '18 at 7:16
  • 1
    $\begingroup$ Welcome to Computer Science! Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. $\endgroup$ – Raphael May 6 '18 at 7:16
  • $\begingroup$ @Raphael because we send to Merge Arry with length n/(2^k) but it return array with min(p,n) elements so we get log(min(p/2^k,n/2^k)) merge that for every one of it the time complexity min(p,n) $\endgroup$ – J.Doe May 6 '18 at 7:29

Your Answer

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

Browse other questions tagged or ask your own question.