Merge sort Algorithm

1.Introduction to Topic
Merge Sort is a well-known method for sorting things that uses a strategy called
divide and conquer. The basic idea is to take a big problem and break it into smaller,
easier parts. In this case, the list that needs to be sorted is split into two halves again
and again until each part has just one item, which is already sorted. This is the
“divide” step. After that, the algorithm starts putting the pieces back together in the
right order — this is the “conquer” step — until everything is sorted.
This way of sorting is known for being fast and reliable, especially when dealing with
large amounts of data. It always works in about the same amount of time, which
makes it more efficient than simpler methods like Bubble Sort or Insertion Sort. One
of the advantages of Merge Sort is that it keeps the order of equal items the same,
which can be important in some situations. The only downside is that it uses extra
space in memory while it's working. Still, because of its consistent performance and
accuracy, Merge Sort is often used when sorting needs to be done well and
efficiently.

2.Purpose and Motivation

The main purpose of Merge Sort is to provide an efficient and reliable way to sort
large amounts of data. Sorting is a fundamental operation in computer science, used
in everything from searching and organizing data to optimizing algorithms. By
breaking a problem into smaller parts and solving each one individually, Merge Sort
ensures that even complex sorting tasks can be completed quickly and correctly.
Key Features of Merge sort:
1. Divide and Conquer Approach: Merge Sort breaks down the problem into
smaller sub-problems (dividing the array), solves them individually (sorts each
half), and then combines them (merges) to get the final sorted result.
2. Stable Sorting Algorithm: It maintains the relative order of equal elements,
which is useful when sorting records based on multiple fields (e.g., sorting by
name while keeping original date order).
3. Consistent Time Complexity – O(n log n): Merge Sort offers predictable and
efficient performance in all cases — best, average, and worst — making it
more reliable than some other algorithms like Quick Sort in worst-case
scenarios.
 4. Applicable to Large Data (External Sorting): Merge Sort is ideal for sorting
huge datasets that don’t fit into memory, making it a popular choice for file-
based sorting (external merge sort).
Merge Sort is a foundational algorithm that demonstrates the power of the
divide and conquer technique. Its merging logic and recursive structure serve as a
base for understanding more advanced algorithmic strategies.

3. Algorithm and Pseudo code

Algorithm: Merge sort
Step 1: Check if the array has more than one element. If yes, proceed with
sorting. If the array has only one element, it's already sorted (base case of
recursion).
Step 2: Divide the array into two halves.
 Find the middle index: mid = (start + end) / 2.
 Split the array into left and right subarrays.
Step 3: Recursively sort the left half of the array.
Step 4: Recursively sort the right half of the array.
Step 5: Merge the two sorted halves.
 Compare elements from both subarrays.
 Place the smaller element into a temporary array.
 Continue until all elements are merged in sorted order.
Step 6: Copy the merged elements back to the original array. Replace the original
part of the array with the merged and sorted values.
Step 7: End the recursion. Once all subarrays are sorted and merged, the full array
will be sorted.

Pseudo Code:
Algorithm MergeSort(array, left, right)
if left < right then
mid ← (left + right) / 2
MergeSort(array, left, mid)
 MergeSort(array, mid + 1, right)
Merge(array, left, mid, right)
Merge(array, left, mid, right)
create empty temporary arrays: leftArray and rightArray
n1 ← mid - left + 1
n2 ← right - mid
for i ← 0 to n1 – 1
leftArray[i] ← array[left + i]
for j ← 0 to n2 - 1
rightArray[j] ← array[mid + 1 + j]
i ← 0, j ← 0, k ← left
while i < n1 and j < n2 do
if leftArray[i] ≤ rightArray[j] then
array[k] ← leftArray[i]
i←i+1
else
array[k] ← rightArray[j]
j←j+1
k←k+1
while i < n1 do
array[k] ← leftArray[i]
i←i+1
k←k+1
while j < n2 do
array[k] ← rightArray[j]
j←j+1
k←k+1
4.Operation of Pseudocode
1. MergeSort Function:
 This function is responsible for dividing the array into smaller parts.
 It checks if the current subarray has more than one element (left < right).
o If yes, it:
 Finds the middle index.
 Recursively calls itself on the left half and right half.
 After both halves are sorted, it calls the Merge function to
combine them.

2. Merge Function:
 This function merges two sorted subarrays (left and right) into one sorted
array.
Here’s how it works:
 It creates two temporary arrays: leftArray and rightArray to store the two
halves.
 Elements from the original array are copied into these temporary arrays.
 Then it compares the elements of both arrays one by one:
o The smaller element is placed into the original array.
 Once one of the temporary arrays is fully copied:
o The remaining elements from the other array are copied into the
original array.

5.Numerical Example
First of all let us consider an array:
[38, 27, 43, 3, 9, 82, 10]
 Merge Sort uses a divide and conquer approach. To solve the given problem, we
first divide the array into two halves. This dividing process is repeated
recursively until each subarray contains only a single element.
 Divide:
 Divide 1:
Here divide the given array into two subarrays by calculating the mid.
Left: [38, 27, 43, 3]
Right: [9, 82, 10]
 Divide 2:
Now divide the subarrays further into halves, and repeat this process until each
subarray contains only a single element.
Left of Left: [38, 27]
Right of Left: [43, 3]
Left of Right: [9, 82]
Right of Right: [10]
 Divide 3:
Break all into single elements:
[38], [27], [43], [3], [9], [82], [10]
Conquer:
Now we merge the small parts back, sorting them as we go:
 Merge [38] and [27]
→ Compare 38 and 27 → [27, 38]
 Merge [43] and [3]
→ Compare 43 and 3 → [3, 43]
 Merge [27, 38] and [3, 43]
→ Compare 27 & 3 → 3
→ Compare 27 & 43 → 27
→ Compare 38 & 43 → 38
→ Remaining: 43
→ Result: [3, 27, 38, 43]
 Merge [9] and [82]
→ Compare 9 and 82 → [9, 82]
 Merge [9, 82] and [10]
→ Compare 9 & 10 → 9
→ Compare 82 & 10 → 10
→ Remaining: 82
→ Result: [9, 10, 82]
Merge:
Now merge [3, 27, 38, 43] and [9, 10, 82]
 Compare 3 & 9 → 3
 Compare 27 & 9 → 9
 Compare 27 & 10 → 10
 Compare 27 & 82 → 27
 Compare 38 & 82 → 38
 Compare 43 & 82 → 43
 Remaining: 82

Final sorted array:

[3, 9, 10, 27, 38, 43, 82]

6.Conclusion:
Merge Sort is a powerful and reliable sorting algorithm that excels in efficiency
and stability. By using the divide and conquer strategy, it breaks down complex
sorting problems into simpler subproblems, making it highly suitable for large
datasets. Unlike some other sorting algorithms, Merge Sort consistently delivers
excellent performance, regardless of the initial order of elements.
Time and Space Complexities:
Time Complexity:
Best, Average, and Worst Case: O(n log n)
Merge Sort always divides the array into halves and then merges them, resulting
in a consistent and efficient time complexity.
Space Complexity:
O(n)
Merge Sort requires additional memory to store temporary subarrays during the
merging process, making it not an in-place algorithm.