Scribd
Upload
4 views1 page

Merge Sort

Merge Sort is a divide-and-conquer sorting algorithm that recursively splits an array into halves, sorts each half, and merges them back together. The algorithm has a time complexity of O(n log n) in all cases and requires O(n) extra space for merging. The process involves dividing the array, recursively sorting the halves, and combining them into a sorted array.

Uploaded by

baishwarn
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
4 views1 page

Merge Sort

Merge Sort is a divide-and-conquer sorting algorithm that recursively splits an array into halves, sorts each half, and merges them back together. The algorithm has a time complexity of O(n log n) in all cases and requires O(n) extra space for merging. The process involves dividing the array, recursively sorting the halves, and combining them into a sorted array.

Uploaded by

baishwarn
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Merge Sort is a classic divide-and-conquer sorting algorithm.

It works by recursively splitting the


array into halves, sorting each half, and then merging them back together.

How Merge Sort Works

1. Divide: Split the array into two halves.


2. Conquer: Recursively sort both halves.
3. Combine: Merge the sorted halves into one sorted array.

MergeSort(A, lb, ub)


{
if (lb < ub)
{
mid = (lb + ub) / 2
mergeSort(A, lb, mid)
mergeSort(A, mid+1, ub)
merge(A, lb, mid, ub)
}

merge (A, lb, mid, ub) if (i > mid)


{ {
i = lb while (j <= ub)
j = mid + 1 {
k = lb B[k] = A[j]
j++, k++
while (i <= mid AND j <= ub) }
{ }
if (A[i] <= A[j]) else
{ {
B[k] = A[i] while (i <= mid)
i++, k++ {
} B[k] = A[i]
else i++, k++
{ }
B[k] = A[j] }
j++, k++
} for (k = lb; k <= ub; k++)
} A[k] = B[k]
}

Time Complexity

 Best Case: O(n log n)


 Average Case: O(n log n)
 Worst Case: O(n log n)

Space Complexity

 O(n) (extra space for merging)

You might also like