Interactive Programming Education Platform

Logic Practice

Merge Sort stands as a pivotal sorting algorithm within the divide-and-conquer algorithm category. It is well-known for its effectiveness and dependability, frequently serving as a standard by which to gauge other sorting algorithms. The key strength of Merge Sort lies in its capacity to effectively arrange an array or list of items, rendering it an indispensable asset in the realms of computer science, data science, and a multitude of other disciplines where data handling plays a crucial role.

A Brief History of Sorting Algorithms

Organizing data is a crucial process in the field of computer science, and the evolution of sorting methods has a deep-rooted past that extends to the initial stages of computing. The progression of sorting algorithms has been influenced by improvements in technology, algorithmic innovations, and the demand for streamlined data handling. This retrospective analysis aims to shed light on the significant breakthroughs and advancements in the realm of sorting algorithms.

1940s and 1950s: Early Beginnings

The initial sorting methods were uncomplicated and depended on fundamental actions. One of the pioneering algorithms introduced was the bubble sort, which consisted of evaluating and exchanging neighboring elements. The early computing machines, like ENIAC and UNIVAC, implemented bubble sort and comparable techniques for arranging data. These algorithms exhibited suboptimal efficiency levels with time complexities of O (n^2).

1950s and 1960s: Algorithm Refinements

As technology advanced, the demand for improved sorting methods became apparent. During the 1950s, John Mauchly, an American mathematician and computer scientist, introduced the merge sort algorithm. Merge sort operates on a divide-and-conquer principle by breaking down the dataset into smaller segments, arranging them, and subsequently recombining them. This approach yielded enhanced efficiency with a time complexity of O(n log n), marking a noteworthy progression in the realm of sorting algorithms.

1960s and 1970s: Quick Sort and Heap Sort

In the 1960s, Tony Hoare, a computer scientist from Britain, presented the quick sort algorithm, which is another sorting method based on the divide-and-conquer approach. Quick sort gained significant popularity because of its rapid speed and effectiveness, frequently surpassing merge sort in real-world scenarios. Nonetheless, it does have a worst-case time complexity of O(n^2), prompting additional exploration into enhancing pivot selection methods.

Around that period, heap sort was created. This method relies on binary heaps, a data structure enabling quick access to the maximum (or minimum) value. Heap sort introduced a different sorting technique with a time complexity of O(n log n) and proved effective for handling extensive datasets.

1970s and 1980s: Radix Sort and Hybrid Algorithms

During the 1970s, radix sort became popular as a non-comparison-based sorting technique that operated on data by analyzing individual digits sequentially. It proved to be highly effective for organizing integers or strings with consistent key lengths. Radix sort demonstrated a linear time complexity in numerous scenarios and was utilized in diverse data manipulation operations.

The 1980s witnessed the rise of hybrid sorting techniques that amalgamated the advantages of various sorting approaches. A notable example of this was IntroSort, a hybrid algorithm that leveraged quicksort initially and transitioned to heapsort after reaching a specific recursion depth. This strategy averted the worst-case scenario for quicksort while harnessing the effectiveness of both sorting algorithms.

Late 20th Century: Introduction of Modern Sorting Algorithms

In the latter part of the 20th century and the beginning of the 21st century, sorting methods such as Timsort and Introspective Sort emerged. Timsort, implemented in Python and Java, merges merge sort and insertion sort to effectively manage practical data sets. Introspective Sort, derived from quicksort, integrates insertion sort to enhance efficiency when processing smaller arrays.

Recent Advances: Parallel and External Sorting

Recent progress in hardware technology and the increasing demand for handling extensive datasets have sparked investigations into parallel and external sorting techniques. Parallel sorting methods take advantage of multi-core CPUs and distributed computing systems to accelerate the sorting process. On the other hand, external sorting approaches are designed to manage datasets that are too large to be accommodated entirely in memory by making use of external storage solutions like hard disk drives or solid-state drives (SSDs) for efficient execution of sorting operations.

In essence, the chronicle of sorting algorithms showcases the progress of computer science and its interaction with hardware advancements and practical data handling requirements. Starting from the modest origins of bubble sort to the sophisticated and tailored sorting algorithms in contemporary use, this progression mirrors the persistent drive to enhance effectiveness in a core computing task: sorting. Ongoing exploration and advancements in sorting algorithms underscore their significance in facilitating efficient organization and processing of data within the constantly growing digital landscape.

The beginnings of Merge Sort can be linked to the early stages of computer science and the creation of sorting algorithms. John von Neumann, a well-known mathematician and computer scientist, is frequently recognized for introducing the idea of merging and sorting around the 1940s. Merge Sort is founded on the divide and conquer strategy, which was established by John von Neumann, laying the groundwork for its evolution as a proficient sorting algorithm.

The enhancement of the algorithm has progressed steadily through the years, benefiting from valuable inputs from different experts in the fields of computer science and mathematics. An early documentation of the Merge Sort algorithm can be found in John Mauchly's 1945 publication "A Method for Merging Information." Grace Hopper also played a role in advancing Merge Sort while working on the UNIVAC I computer in the 1950s.

In the 1960s, Merge Sort was integrated by Donald Knuth into the initial volume of his renowned literary series, "The Art of Computer Programming," establishing its position among the recognized sorting algorithms. Over the years, Merge Sort has upheld its significance and widespread adoption in sorting algorithms landscape thanks to its effective performance and reliability.

Algorithmic Overview:

✅ Merge Sort is a divide-and-conquer algorithm, which means it breaks down a problem into smaller subproblems, solves them, and then combines the solutions to solve the original problem. The primary steps of the Merge Sort algorithm can be summarized as follows:
✅ Divide: The unsorted array is divided into two halves (or more) until each subarray contains only one element. This is the base case of the recursion.
✅ Conquer: The subarrays are recursively sorted. This is typically done by applying the Merge Sort algorithm to each subarray, which involves further division and sorting.
✅ Merge: The sorted subarrays are then merged back together to produce a single, sorted array. This step is where the algorithm gets its name.

The efficiency of Merge Sort lies in its merging phase, where it merges pre-sorted subarrays into one fully sorted array. This merging operation involves comparing elements from the two subarrays and arranging them in the appropriate sequence within the merged array. By doing so, it guarantees that the elements are correctly ordered in each subarray and ultimately in the final sorted array.

Recursive Nature:

Merge Sort's recursive characteristic is a key aspect of the algorithm. It iteratively breaks down the main problem into smaller subtasks until it hits a base scenario, where every subarray consists of just a single item. In this scenario, a subarray containing a single item is already deemed sorted, initiating the merging process of the subarrays.

The recursive nature of Merge Sort can be depicted as a binary tree. Initially, the unsorted array serves as the root of the tree. As recursion progresses, the array gets segmented into smaller subarrays, forming a binary tree layout. The terminal nodes of this tree symbolize the single-element subarrays, inherently classified as sorted.

Merge Sort Time Complexity:

One of the most attractive aspects of Merge Sort is its consistent and efficient time complexity. Merge Sort exhibits a time complexity of O(n log n) in all cases, making it a dependable choice for sorting large datasets. Let's explore why this is the case:

✅ Divide: The divide step involves repeatedly dividing the array into two halves until we have one-element subarrays. This process takes O(log n) time since the array is divided in half at each step.
✅ Conquer: In the conquer step, each subarray is sorted independently. Since every element is visited once during the merge process, the time complexity for sorting the subarrays is O(n) for each level of recursion.
✅ Merge: The merge step takes O(n) time to combine two subarrays of size n/2 into a single sorted subarray. The merging process efficiently combines the two halves while preserving the order of the elements.

When all these steps are combined, the Merge Sort algorithm demonstrates a time complexity of O(n log n). This reliable and effective efficiency is a key factor behind the preference for Merge Sort in real-world applications.

Merge Sort Space Complexity:

The memory usage of an algorithm, known as space complexity, indicates the memory it consumes while running. Even though Merge Sort is known for its time efficiency, it does necessitate extra memory for the merging phase. This characteristic renders it a reliable and flexible sorting method, albeit not an in-place sorting algorithm.

The space complexity of Merge Sort amounts to O(n) as it necessitates extra memory to accommodate the two halves during the merging phase. This additional memory is crucial for temporarily storing the combined outcomes as they are merged. Essentially, Merge Sort entails using supplementary memory that scales in proportion to the input data's size, posing potential challenges when handling extensive datasets.

Nevertheless, it is crucial to highlight that the extra storage space utilized by Merge Sort is independent of the exact configuration of items in the initial array. This characteristic renders Merge Sort stable and adjustable. Stability represents a favorable attribute in sorting methodologies as it guarantees that identical elements preserve their sequence in the finalized output.

To address the concern of space complexity, a different strategy referred to as "bottom-up" or "iterative" Merge Sort can be employed. This method minimizes the space complexity to O(1) through meticulous handling of the merging operation and rearranging elements within the initial array. Despite enhancing space efficiency, this technique may be less straightforward and slightly more intricate to execute.

Merge Sort Implementation:

Merge Sort is a flexible algorithm that is applicable across different programming languages. To demonstrate how it works, we will examine a Python example at a high level. The following C++ code adheres to the procedural instructions of the Merge algorithm:

Example


// C++ program for Merge Sort
#include <bits/stdc++.h>
using namespace std;
// Merges two subarrays of array[].
// First subarray is arr[begin..mid]
// Second subarray is arr[mid+1..end]
void merge(int array[], int const left, int const mid,
		int const right)
{
	int const subArrayOne = mid - left + 1;
	int const subArrayTwo = right - mid;

	// Create temp arrays
	auto *leftArray = new int[subArrayOne],
		*rightArray = new int[subArrayTwo];

	// Copy data to temp arrays leftArray[] and rightArray[]
	for (auto i = 0; i < subArrayOne; i++)
		leftArray[i] = array[left + i];
	for (auto j = 0; j < subArrayTwo; j++)
		rightArray[j] = array[mid + 1 + j];

	auto indexOfSubArrayOne = 0, indexOfSubArrayTwo = 0;
	int indexOfMergedArray = left;

	// Merge the temp arrays back into array[left..right]
	while (indexOfSubArrayOne < subArrayOne
		&& indexOfSubArrayTwo < subArrayTwo) {
		if (leftArray[indexOfSubArrayOne]
			<= rightArray[indexOfSubArrayTwo]) {
			array[indexOfMergedArray]
				= leftArray[indexOfSubArrayOne];
			indexOfSubArrayOne++;
		}
		else {
			array[indexOfMergedArray]
				= rightArray[indexOfSubArrayTwo];
			indexOfSubArrayTwo++;
		}
		indexOfMergedArray++;
	}

	// Copy the remaining elements of
	// left[], if there are any
	while (indexOfSubArrayOne < subArrayOne) {
		array[indexOfMergedArray]
			= leftArray[indexOfSubArrayOne];
		indexOfSubArrayOne++;
		indexOfMergedArray++;
	}
	// Copy the remaining elements of
	// right[], if there are any
	while (indexOfSubArrayTwo < subArrayTwo) {
		array[indexOfMergedArray]
			= rightArray[indexOfSubArrayTwo];
		indexOfSubArrayTwo++;
		indexOfMergedArray++;
	}
	delete[] leftArray;
	delete[] rightArray;
}

// begin is for left index and end is right index
// of the sub-array of arr to be sorted
void mergeSort(int array[], int const begin, int const end)
{
	if (begin >= end)
		return;

	int mid = begin + (end - begin) / 2;
	mergeSort(array, begin, mid);
	mergeSort(array, mid + 1, end);
	merge(array, begin, mid, end);
}

// UTILITY FUNCTIONS
// Function to print an array
void printArray(int A[], int size)
{
	for (int i = 0; i < size; i++)
		cout << A[i] << " ";
	cout << endl;
}

// Driver code
int main()
{
	int arr[] = { 12, 11, 13, 5, 6, 7 };
	int arr_size = sizeof(arr) / sizeof(arr[0]);

	cout << "Given array is \n";
	printArray(arr, arr_size);

	mergeSort(arr, 0, arr_size - 1);

	cout << "\nSorted array is \n";
	printArray(arr, arr_size);
	return 0;
}

Output:

Output


Given array is 
12 11 13 5 6 7 
Sorted array is 
5 6 7 11 12 13 
................
Process executed in 1.11 seconds
Press any key to continue

Explanation

✅ #include <bits/stdc++.h> and using namespace std;: These lines include the necessary C++ standard libraries and specify that the code will use the standard namespace for convenience.
✅ void merge(int array, int const left, int const mid, int const right): This function is responsible for merging two subarrays of the input array. It takes three parameters: array: The input array to be sorted. left: The left index of the first subarray. mid: The middle index that separates the two subarrays. right: The right index of the second subarray.
✅ The next lines in the merge function: Calculate the sizes of the two subarrays. Create temporary arrays leftArray and rightArray to store the data from the two subarrays. Copy the data from the original array into these temporary arrays.
✅ The while loop in the merge function merges the two subarrays by comparing elements from both subarrays and placing them in the correct order in the original array.
✅ After merging, there are two while loops that copy any remaining elements from the leftArray and rightArray to the original array.
✅ Finally, delete is used to free the memory allocated for the temporary arrays.
✅ void mergeSort(int array, int const begin, int const end): This is the merge sort function. It takes three parameters: array: The input array to be sorted. begin: The left index of the subarray to be sorted. end: The right index of the subarray to be sorted.
✅ In the mergeSort function, if begin is greater than or equal to end, it returns, as there's nothing to sort in this case.
✅ The function calculates the middle index mid and then recursively calls itself on the left and right subarrays and finally merges them using the merge function.
✅ The printArray function is a utility function to print the elements of an array.
✅ In the main function: An example integer array arr is defined. The size of the array is calculated using sizeof. The original array is printed. mergeSort is called to sort the array. The sorted array is printed.
✅ array: The input array to be sorted.
✅ left: The left index of the first subarray.
✅ mid: The middle index that separates the two subarrays.
✅ right: The right index of the second subarray.
✅ Calculate the sizes of the two subarrays.
✅ Create temporary arrays leftArray and rightArray to store the data from the two subarrays.
✅ Copy the data from the original array into these temporary arrays.
✅ array: The input array to be sorted.
✅ begin: The left index of the subarray to be sorted.
✅ end: The right index of the subarray to be sorted.
✅ An example integer array arr is defined.
✅ The size of the array is calculated using sizeof.
✅ The original array is printed.
✅ mergeSort is called to sort the array.
✅ The sorted array is printed.

The code illustrates the procedure of Merge Sort for arranging an integer array.

Time and Space Complexity

Time Complexity:

Merge Sort is a divide-and-conquer sorting algorithm, and its time complexity can be analyzed as follows:

✅ Divide Step: In this step, the array is divided into two equal-sized subarrays. This process continues recursively until we reach subarrays of size 1. The number of divisions required is approximately O(log n), where n is the number of elements in the array.
✅ Conquer Step: In the conquer step, we merge two subarrays of size n/2 each, which takes O(n) time. Since we have O(log n) levels of recursion, and each level takes O(n) time, the total time complexity of the merge operation is O(n * log n).
✅ Overall Time Complexity: The divide and conquer steps result in a time complexity of O(n * log n) for the Merge Sort algorithm in the worst, best, and average cases. This makes Merge Sort very efficient for large datasets.

Space Complexity:

The space complexity of an algorithm refers to the amount of additional memory required to perform the algorithm. In the case of the Merge Sort code, we use additional memory for the following purposes:

✅ Temporary Arrays: The code uses two temporary arrays, leftArray and rightArray, to store the elements of the subarrays during the merge step. Each of these arrays has a size of approximately n/2. Therefore, the space complexity due to these temporary arrays is O(n).
✅ Recursive Call Stack: Merge Sort is a recursive algorithm, and each recursive call creates a new set of local variables and memory for function call data. The maximum depth of the recursion tree is O(log n), and at each level, we have space used for function parameters and local variables. The total space used in the call stack is also O(log n).
✅ Overall Space Complexity: The space complexity of Merge Sort is O(n) for the temporary arrays plus O(log n) for the call stack. Therefore, the overall space complexity is O(n + log n), which can be simplified to O(n).

In essence, the Merge Sort algorithm operates with a time complexity of O(n * log n) and a space complexity of O(n) across all scenarios - worst, best, and average cases. Its space complexity is influenced by the utilization of temporary arrays and the recursive characteristics inherent in the algorithm. Despite demanding extra memory for operation, Merge Sort proves to be effective due to its favorable time complexity, especially when sorting extensive datasets.

Advantages of Merge Sort:

✅ Stable Sorting: Merge Sort is a stable sorting algorithm, which means that the relative order of equal elements is preserved during the sorting process. This is essential when sorting data based on multiple criteria or when the original order of equal elements needs to be maintained.
✅ Efficient for Large Datasets: Merge Sort has a time complexity of O(n log n) in the worst, best, and average cases. This property makes it particularly efficient for sorting large datasets. Unlike other algorithms with quadratic time complexity, such as Bubble Sort or Insertion Sort, Merge Sort's performance does not degrade significantly with increasing input size.
✅ Guaranteed Performance: Unlike some other sorting algorithms, Merge Sort's time complexity remains constant regardless of the data distribution. Its divide-and-conquer strategy ensures that it consistently divides the data into balanced partitions, leading to a predictable performance.
✅ Parallelizability: Merge Sort can take advantage of parallel processing to speed up sorting, making it suitable for modern multi-core and distributed computing environments. By dividing the sorting process into smaller subproblems, these sub problems can be sorted concurrently.
✅ No Worst-Case Scenario: Merge Sort does not have a worst-case scenario like Quick Sort, where the algorithm's performance can degrade significantly for specific data distributions. Its time complexity remains stable at O (n log n) across all cases.

Disadvantages of Merge Sort:

✅ Space Complexity: Merge Sort requires additional memory to store temporary arrays during the merging phase. This means it has a space complexity of O(n), which could be a concern when sorting very large datasets with limited memory resources.
✅ Slower for Small Datasets: While Merge Sort is highly efficient for large datasets, its divide-and-conquer nature and the overhead of function calls make it relatively slower for small datasets compared to simpler algorithms like Insertion Sort or Selection Sort.
✅ Non-Adaptive: Merge Sort does not take advantage of any existing order in the dataset. Even if the array is partially sorted, Merge Sort will still perform its standard divide-and-conquer approach, resulting in a higher number of operations.
✅ Recursive Overhead: Merge Sort is typically implemented using recursion, which adds some overhead due to function calls and maintaining the call stack. In some programming languages or platforms, recursion might not be the most efficient way to implement sorting algorithms.

In essence, the strengths of Merge Sort are found in its effectiveness, reliability, and consistent execution, positioning it as a superb option for arranging extensive data sets and situations where stability holds significant importance. Conversely, its drawbacks include space usage, lack of adaptability, and comparatively sluggish operation when handling smaller datasets. Ultimately, the selection of a sorting algorithm is dictated by the unique demands and attributes of the dataset under consideration.

Applications of merge sort

Merge Sort is a versatile sorting algorithm with various applications across different domains due to its efficiency and stability. Its O (n log n) time complexity and ability to maintain the relative order of equal elements in the input make it well-suited for numerous tasks. Here are some of the prominent applications of Merge Sort:

✅ General Sorting: Merge Sort is commonly used for sorting large datasets in various applications, such as database management systems, file processing, and data analysis. Its stable nature ensures that the original order of equal elements remains intact in the sorted output.
✅ External Sorting: Merge Sort is ideal for sorting large files that do not fit entirely in memory, a scenario known as external sorting. By dividing the data into manageable chunks, sorting each segment, and then merging them together, Merge Sort minimizes the need for excessive memory usage.
✅ Parallel Processing: Merge Sort's divide-and-conquer nature lends itself well to parallelization. Different subarrays can be sorted concurrently on separate processors or threads, taking advantage of multi-core architectures to improve sorting performance.
✅ Inversion Counting: Merge Sort is efficient for counting inversions in an array, where an inversion represents a pair of elements in the wrong order. This is useful in applications such as measuring the similarity between two sequences or identifying data anomalies.
✅ Searching Algorithms: Merge Sort is a fundamental component in various searching algorithms, such as binary search in sorted arrays. By ensuring that the array remains sorted, binary search can efficiently find specific elements.
✅ Merge Operations in Data Structures: Merge Sort's merging step is also widely used in data structure operations like merging two sorted linked lists or merging intervals in interval trees.
✅ Merge-Based Divide-and-Conquer Algorithms: Several advanced algorithms, like Merge Sort for sorting networks, use the merging technique as a building block. These algorithms often exhibit superior performance for specific tasks.
✅ External Memory Applications: Merge Sort is prevalent in applications that handle data stored on external storage devices, like hard drives or solid-state drives. Its ability to reduce the number of disk I/O operations makes it an essential component in external memory algorithms.
✅ Merge Join in Database Operations: In database systems, Merge Sort is used in merge join operations to combine and retrieve data efficiently from two sorted tables based on certain conditions.
✅ Offline Algorithms: Merge Sort is used in various offline algorithms, where the entire input is available at the start, allowing for efficient preprocessing before executing the main algorithm.

In essence, the effectiveness, reliability, and versatility of Merge Sort render it a commonly applied and beneficial sorting algorithm across different domains, ranging from standard sorting tasks to intricate data manipulation and storage operations.

Merge Sort Algorithm In C++