Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.
2 edited tags
| link
1
source | link

How to find Time complexity of merge sort with parameter?

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.