Scribd
Upload
2 views1 page

02 Merge Sort

Merge sort is a divide and conquer sorting algorithm that achieves O(n log n) time complexity in all cases. It is stable and particularly effective for large datasets and applications requiring predictable performance. The algorithm involves recursively dividing input into smaller parts, sorting them, and merging the results.

Uploaded by

- पार्थ ‹𝅮.
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views1 page

02 Merge Sort

Merge sort is a divide and conquer sorting algorithm that achieves O(n log n) time complexity in all cases. It is stable and particularly effective for large datasets and applications requiring predictable performance. The algorithm involves recursively dividing input into smaller parts, sorting them, and merging the results.

Uploaded by

- पार्थ ‹𝅮.
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Merge Sort: A Research Note

Abstract
Merge sort is a comparison-based sorting algorithm based on divide and conquer. It divides a sequence into
smaller parts, recursively sorts them, and merges the sorted results.

Introduction
Efficient sorting is important in databases, search systems, data processing, and many other applications.
Merge sort provides predictable O(n log n) performance.

Method
The input is divided approximately in half until subarrays contain one element. Sorted subarrays are then
merged by repeatedly selecting the smaller front element.

Complexity
Merge sort has O(n log n) time complexity in the best, average, and worst cases. A conventional
implementation requires O(n) auxiliary space.

Properties and Applications


Merge sort is stable when equal elements preserve their relative order. It is useful for large datasets, linked
lists, external-memory sorting, and parallel processing.

Conclusion
Merge sort combines strong asymptotic performance with stability and predictable execution time.

You might also like