Introduction

Merge Sort Technique: Merge Sort is a highly efficient sorting algorithm that follows the divide-and-conquer strategy. The algorithm divides the array into smaller subarrays, sorts each subarray, and merges them back together in a sorted manner.
This technique gets its name because it merges sorted subarrays into a single sorted array.

How can we sort an array?

• In Merge Sort, we divide the array into two halves recursively until each subarray contains only one element.
• Each subarray is sorted independently.
• The sorted subarrays are merged together by comparing their elements and placing them in the correct order.
• The merging process continues until the entire array is sorted.

Important Observations

• After dividing, the smallest subarrays contain only one element and are inherently sorted.
• During the merging phase, elements from two sorted subarrays are compared and placed into the final sorted array.
• The algorithm works efficiently for large datasets.
• The array will be sorted in ascending order after the merge process is complete.

Key Characteristics:

• Divide-and-conquer sorting technique.
• Uses additional space for temporary arrays during merging.
• Stable algorithm (preserves the order of equal elements).
• Efficient for sorting large datasets.

Advantages:

• Efficient for large datasets.
• Time complexity is (O(n log n)) in all cases.
• Stable sorting algorithm.

Disadvantages:

• Requires additional memory for merging subarrays.
• Not an in-place sorting algorithm.

Time Complexity:

• Best Case: (O(n log n)).
• Average Case:(O(n log n)).
• Worst Case: (O(n log n)).