Merge Sort in Data Structures and Algorithms: With Implementation in C++/Java/Python

Amit Kumar Ghosh 18 min read

15 Sep 2023

Intermediate

499 Views

Merge Sort in Data Structure: An Overview

Data structures are the key components of every computer program or software application. Understanding and implementing them effectively is the cornerstone to achieving efficient solutions. One important data structure known as Merge Sort is a technique that helps us sort elements in an array, list, or another linear sequence, in order to make searching for items easier and faster. In this article, we'll explain how Merge Sort works, Merge sort in data structures example, Merge sort program in data structures, merge sort algorithm, and guide you through its implementation step by step with detailed examples.

What is the Merge Sort Algorithm in Data Structure?

Merge Sort is a well-known sorting algorithm in the world of data structure. It is characterized by its fast, efficient, and stable sorting technique. Merge sort involves dividing a given list into smaller sub-lists, sorting them, and then combining them back into a larger, sorted list. This divide-and-conquer approach ensures that the algorithm is efficient for large data sets. Because it is reliable and effective at sorting huge datasets, merge sort is a common data structure. It is crucial for software developers as well as data analysts since it preserves the original order of equal items and is widely utilized in computer science, engineering, & finance.

How does Merge Sort Works?

Merge sort is a sorting algorithm that works by dividing an unsorted array into smaller arrays, sorting the smaller arrays, and then merging them back together. Here's how merge sort works:

Divide the unsorted array into two halves, called left and right.

Recursively sort the left half and the right half using merge sort.

Merge the two sorted halves back together.

To explain step 3, let's say we have two sorted arrays: A and B. We want to merge them into a single sorted array. Here's how we can do it:

Create an empty array, called C, to store the merged result.
Compare the first elements of A and B. If the first element of A is smaller, add it to C and remove it from A. Otherwise, add the first element of B to C and remove it from B.
Repeat step 2 until A and B are both empty.
Return C as the merged result.

Merge Sort Complexity

Time Complexity

Best Case Complexity: When the array is already sorted and no more sorting is necessary. Merge sort's best-case time complexity is O(n*logn).
Average Case Complexity: It happens when the array elements are arranged erratically and improperly in ascending and descending order. Merge sort has an O(n*logn) case time complexity on average.
Worst Case Complexity: This is what happens when array elements must be sorted in reverse. The array's elements are in descending order, therefore let's say you need to sort them in ascending order. Merge sort has a worst-case time complexity of O(n*logn).

Space Complexity

The merge sort has an O(n) space complexity. It's because a second variable is needed for swapping in merge sort.

Application of Merge Sort in Data Structure

Sorting: As mentioned, merge sort is primarily used for sorting arrays of elements. It can efficiently sort large arrays of numbers or strings, making it a popular choice for sorting algorithms in programming.
External Sorting: Merge sort is also used for external sorting, which is a type of sorting that involves data sets that are too large to fit into memory. In external sorting, the data is divided into smaller chunks that can be sorted separately and then merged together.
Database Operations: Merge sort is used in various database operations, such as sorting data before performing a search or merging two sets of data. It is also used in indexing and for optimizing certain queries.
Parallel Processing: Merge sort can be used for parallel processing, which involves dividing a task into smaller parts that can be processed simultaneously. Merge sort can be divided into smaller sub-tasks that can be executed in parallel, improving overall efficiency and reducing the time for sorting.
Computer Graphics: Merge sort can be used for depth sorting in computer graphics, which involves determining the order in which objects should be drawn to create a 3D image. Merge sort can be used to sort the objects based on their distance from the viewer, improving the overall visual quality of the image

Merge Sort Algorithm in Data Structure

MergeSort(A, p, r):
    if p > r 
        return
    q = (p+r)/2
    mergeSort(A, p, q)
    mergeSort(A, q+1, r)
    merge(A, p, q, r)

Implementation of Merge Sort in Data Structure

 
 # MergeSort in Python
 def mergeSort(array):
 if len(array) > 1:
 # r is the point where the array is divided into two subarrays
 r = len(array)//2
 L = array[:r]
 M = array[r:]
 # Sort the two halves
 mergeSort(L)
 mergeSort(M)
 i = j = k = 0
 # Until we reach either end of either L or M, pick larger among
 # elements L and M and place them in the correct position at A[p..r]
 while i < len(L) and j < len(M):
 if L[i] < M[j]:
 array[k] = L[i]
 i += 1
 else:
 array[k] = M[j]
 j += 1
 k += 1
 # When we run out of elements in either L or M,
 # pick up the remaining elements and put in A[p..r]
 while i < len(L):
 array[k] = L[i]
 i += 1
 k += 1
 while j < len(M):
 array[k] = M[j]
 j += 1
 k += 1
 # Print the array
 def printList(array):
 for i in range(len(array)):
 print(array[i], end=" ")
 print()
 # Driver program
 if __name__ == '__main__':
 array = [ 7, 5, 1, 6, 10]
 mergeSort(array)
 print("Sorted array is: ")
 printList(array)

 
public class MergeSort {
 public static void mergeSort(int[] array) {
 if (array.length > 1) {
 int mid = array.length / 2;
 int[] left = new int[mid];
 int[] right = new int[array.length - mid];
 // Copy elements to left and right subarrays
 for (int i = 0; i < mid; i++) {
 left[i] = array[i];
 }
 for (int i = mid; i < array.length; i++) {
 right[i - mid] = array[i];
 }
 // Recursive calls to sort left and right subarrays
 mergeSort(left);
 mergeSort(right);
 int i = 0, j = 0, k = 0;
 // Merge left and right subarrays
 while (i < left.length && j < right.length) {
 if (left[i] < right[j]) {
 array[k] = left[i];
 i++;
 } else {
 array[k] = right[j];
 j++;
 }
 k++;
 }
 // Copy remaining elements from left subarray
 while (i < left.length) {
 array[k] = left[i];
 i++;
 k++;
 }
 // Copy remaining elements from right subarray
 while (j < right.length) {
 array[k] = right[j];
 j++;
 k++;
 }
 }
 }
 public static void printArray(int[] array) {
 for (int i = 0; i < array.length; i++) {
 System.out.print(array[i] + " ");
 }
 System.out.println();
 }
 public static void main(String[] args) {
 int[] array = {7, 5, 1, 6, 10};
 mergeSort(array);
 System.out.println("Sorted array is:");
 printArray(array);
 }
}

 
#include <iostream>
#include 
#include 
void merge(std::vector& array, std::vector& left, std::vector& right) {
 int i = 0, j = 0, k = 0;
 int leftSize = left.size();
 int rightSize = right.size();
 while (i < leftSize && j < rightSize) {
 if (left[i] < right[j]) {
 array[k] = left[i];
 i++;
 } else {
 array[k] = right[j];
 j++;
 }
 k++;
 }
 while (i < leftSize) {
 array[k] = left[i];
 i++;
 k++;
 }
 while (j < rightSize) {
 array[k] = right[j];
 j++;
 k++;
 }
}
void mergeSort(std::vector& array) {
 int size = array.size();
 if (size > 1) {
 int mid = size / 2;
 std::vector left(array.begin(), array.begin() + mid);
 std::vector right(array.begin() + mid, array.end());
 mergeSort(left);
 mergeSort(right);
 merge(array, left, right);
 }
}
void printArray(const std::vector& array) {
 for (int i = 0; i < array.size(); i++) {
 std::cout << array[i] << " ";
 }
 std::cout << std::endl;
}
int main() {
 std::vector array = {7, 5, 1, 6, 10};
 mergeSort(array);
 std::cout << "Sorted array is:" << std::endl;
 printArray(array);
 return 0;
}

Explanation

The Merge Sort method is used to sort an array in this example. The array is split into smaller pieces, sorted, and then joined back together in a sorted manner. The result is a printed copy of the sorted array.

Output

Sorted array:
1, 5, 6, 7, 10

Advantages of Merge Sort in Data Structure

Stable Sorting: Merge sort is a stable sorting algorithm, meaning that it preserves the relative order of equal elements in the input array. This makes it useful in certain applications, such as sorting arrays of records with multiple fields.
Good Performance: Merge sort has a time complexity of O(nlogn), which makes it efficient for sorting large datasets. It also performs well in parallel processing environments, where multiple threads can be used to sort different sub-arrays simultaneously.
No Worst-Case Scenario: Unlike some other sorting algorithms, such as quicksort, merge sort has no worst-case scenario. Its worst-case time complexity is always O(nlogn), regardless of the input data.
Easy to Implement: Merge sort is relatively easy to implement, even for beginners. The algorithm is based on the divide-and-conquer paradigm, which can be expressed recursively.
Memory Efficiency: Merge sort is a stable, in-place sorting algorithm, which means that it can sort data without requiring extra memory space. In contrast, algorithms like quicksort require additional memory space to perform the sorting operation

Disadvantages of Merge Sort in Data Structure

Space Complexity: Merge Sort has a space complexity of O(n), which means it requires extra memory space to store the temporary sub-arrays. This can be a disadvantage if the system has limited memory resources or if the size of the input data is very large.
Not In-place: Merge Sort is not an in-place sorting algorithm, which means that it requires extra memory space to store the temporary sub-arrays during the sorting process. This can be a disadvantage if the system has limited memory resources or if the size of the input data is very large.
Complexity: While Merge Sort has a time complexity of O(n log n), it may not be the most efficient sorting algorithm in all scenarios. For example, if the size of the input data is very small, a simpler algorithm such as insertion sort may be more efficient.
Recursive: Merge Sort is a recursive algorithm, which means that it calls itself repeatedly until the sorting is complete. This can lead to stack overflow errors or other performance issues if the input data is very large.
Not adaptive: Merge Sort is not an adaptive sorting algorithm, which means that its performance does not change significantly based on the initial order of the input data. This can be a disadvantage in scenarios where the input data is already partially sorted or nearly sorted.

FAQs

1. What is the Merge sort in data structures example?

An array is split into smaller halves, sorted recursively, and then merged using the sorting method known as merge sort. For instance, Merge Sort would divide [7, 5, 1, 6, 10] into [7, 5, 1] & [6, 10], sort them, then combine them to form [1, 5, 6, 7, 10].

2. Which data structure is best for merge sort?

Different data structures can be used to implement merge sort, however, they typically operate best with arrays or linked lists.

3. Why do we use merge sort in data structure?

Merge Sort is a valuable tool for many applications in computer science, engineering, & finance because of its stability and effectiveness in sorting enormous datasets.

4. How many types of merge sort are there?

Although there is often just one primary type of Merge Sort algorithm, it can be customized and improved in a number of ways for certain use cases and data formats.

5. What are the two functions of Merge Sort in Data Structure?

The array is split into smaller halves by the Merge Sort algorithm, and these smaller halves are then merged back together in sorted order.

Summary

In conclusion, the merge sort in the data structure is an incredibly powerful tool for sorting large amounts of data. It's simple to understand and execute, and its operations are done in a fraction of the time other algorithms require. Its stability means it can be used when order matters, such as sorting by customer ID. Merge sort allows businesses to quickly sort through their data and better react to customer-related needs. We hope this article has helped you understand why it is critical to have a sound understanding of how merge sort works and its benefits.

01 Beginner

02 Intermediate

03 Advanced

04 Training Programs