Merge Sort for Linked Lists and Arrays

Introduction

This article introduces, explains, and evaluates the sorting method Merge Sort. This post’s objective is to arm you with thorough background knowledge of the Merge Sort Algorithm, which serves as a building block for more intricate algorithms.

Merge Sort is a simple and fundamental algorithm in Computer Science. Being familiar with it will help you understand the aspects to consider when selecting the most effective algorithm for data-related activities. The Merge Sort algorithm was created in 1945 by John Von Neumann using the divide-and-conquer approach.

Divide and Conquer

To understand the Merge Sort, let us first understand the Divide and Conquer Paradigm along with the programming concept of Recursion. Recursion is a concept where the function created keeps calling itself until a condition is met.

The Divide and Conquer algorithm, such as Merge Sort, uses this concept of Recursion to solve specific problems. Divide and Conquer algorithms break down larger problems into smaller sub-problems, applying a predetermined solution recursively to each element. Then, after recombining the answers from each sub-part, the overall problem is solved.

The Divide and Conquer technique is essentially the combination of three steps, i.e.

• Breaking Down the larger problem into smaller sub-parts (Divide)
• Solving the smaller sub-problem by the recursive use of functions (Conquer)
• Combining each of the smaller subproblems to get the final solution. (Combine)

Merge Sort

The Merge Sort method recursively breaks the array into half, gradually breaking them into smaller parts. After comparing smaller halves and combining them in ascending order, the final sorted array is created.

Steps and Implementation

The Merge Sort method is implemented in three stages. Divide, Conquer, and Combine your forces.

The first phase in the Divide-and-Conquer strategy is to divide. This first step divides the entire array into two smaller halves. The arrays are then split down further until they can no longer be divided, i.e. they contain only a single element. Now each half-array has only one element.

The recursive loop in Merge Sort’s second phase is concerned with sorting the array’s elements in ascending order.

The Merge Sort algorithm’s division, comparison, and combination processes are depicted in the diagram above. Credits

Algorithm

Pseudo Code for Merge Sort

Code

Space and Time Complexity

Let the Time Complexity of Merge Sort for sorting n integers be T(n).
Then, the Time Complexity of Sorting n/2 integers will be T(n/2)

The Time Complexity to merge two sorted arrays of size n/2 each to get a sorted array of size n is O(n).

Therefore, the following recurrence relation can be given i.e.

T(n) = 2T(n/2) + O(n)

Similarly,

T(n/2) = 2T(n/4) + O(n/2)

Therefore,

T(n) = 4T(n/4) + O(n) + 2O(n/2)

In general, we can write the following expression,

T(n) = 2^k * T(n/(2^k)) + k * O(n)

On substituting k by log n, we get

T(n) = n * T(1) + n * log n

Thus,

T(n) = O(n log n)

Since Merge Sort takes a similar number of steps in each iteration, it takes an equal amount of time to sort the Best Case, Average Case and Worst Case Array.

Merge Sort creates an additional array of size equal to the sum of the size of the left and right arrays. Therefore, it uses O(n) extra space to sort the array.

Advantages

• Merge Sort is quicker than other sorting algorithms like Insertion Sort and Bubble Sort because it sorts the array in O(n log n) time instead of O(n²) time taken by these algorithms.
• Merge Sort has a consistent running time because it takes a similar time in all the stages regardless of whether the array is already sorted or not.
• Merge Sort is a stable sorting algorithm.

Disadvantages

• Merge Sort goes through the whole array even if the array is sorted, taking O(n log n) time, unlike Insertion Sort, which takes O(n) time for a sorted array.
• Merge Sort uses more memory space to store the sub-elements of the initial split array. Due to this, Quick Sort is preferred over Merge Sort.
• The standard algorithm for Merge Sort is not an in-place sorting algorithm.

MergeSort for Linked List

Merge Sort is the best choice to sort a linked list compared to other algorithms. Unlike arrays, we can insert elements in Linked List at any place given the previous pointer, in O(1) space and O(1) time complexity.

Therefore, we can implement Merge Sort without extra space for linked lists, which is the preferred sorting technique in the case of linked lists.

Conclusion

We can conclude from the above discussion that Merge Sort is a beneficial Sorting Technique in the case of Linked Lists. In contrast, in-place array sorting techniques like Quick Sort have a higher preference than Merge Sort.