Merge Sort

As we have seen previously that the running time of insertion sort is bounded by θ(n2). Now we are interested in finding an algorithm that works better than insertion sort. Merge sort performs faster than insertion sort and it uses divide-and-conquer paradigm. So, what is divide-and-conquer paradigm?

Divide: Divide the given problem into a number of subproblems that are smaller instances of the given problem.
Conquer: Solve the problem recursively and when the size of problem becomes small enough then, solve it in the straight forward manner.
Combine: Combine the solution of the subproblems to obtains the solution to the original problem.

Divide-and-conquer paradigm applied to merge sort:
Divide: Divide the given sequence of n-elements into two sequences with nearly half elements.
Conquer: Sort the two sequences recursively using merge sort.
Combine: Merge the two sorted sequence to produce the solution to the combined sequence.

Now, let’s understand the merge sort algorithm using an example from CLRS book Introduction to Algorithms. Suppose you have two piles of cards each of which are in sorted order. We want to combine these two piles into a single sorted output pile. To do this, we compare the cards on the top of each pile. The smaller one is picked (and a new card is exposed) and kept on the output pile with its face down. We repeat the process until one of the pile becomes empty and we keep the remaining pile directly on the output pile. In this way, a sorted pile of card is obtained.

At first, we write the MERGE procedure which merges two sorted sequences. We use a sentinel value ∞ which indicates that one of the sequences has been empty. It also makes sense as the value of the sequences will never be greater than ∞. While implementing the pseudocode in a programming language, we can replace ∞ by any value which is greater than the maximum value in the whole sequence.
MERGE (A,p,q,r)       //p and r are indices to the first and last elements of the array A
1.      n1 = q – p + 1
2.      n2 = r – q
3.      Let L[1..n1+1] and R[1..n2+1] be new arrays   //one extra memory in each array for sentinel
4.      for i = 1 to n1
5.               L[i] = A[p + i -1]
6.      for j = 1 to n2
7.               R[j] = A[q + j]
8.      L[n1 + 1] = ∞
9.      R[n2 + 1] = ∞
10.  i = 1
11.  j = 1
12.  for k = p to r
13.           if L[i] < R[j]
14.                       A[k] = L[i]
15.                       i = i + 1
16.           else A[k] = R[j]
17.                       j = j + 1

To determine the running time of MERGE procedure, let us consider line 13 as a barometer instruction (i.e. the instruction which is executed most). All other instruction outside for loop takes constant time. The for loops in line 4 and 6 takes θ (n1 + n2) = θ (n) time. The for loop in line 12 is executed n times so, it takes θ (n) time. Hence, merge sort takes θ (n) time.
MERGE-SORT (A, p, r)
1.      if p < r
2.              q = L(p + r) / 2˩
3.              MERGE-SORT (A, p, q)
4.              MERGE-SORT (A, q + 1, r)
5.              MERGE (A, p, q, r)

If p > r, the subarray has at most one element and is therefore already sorted. Let t (n) be the time taken by this algorithm to sort an array of n elements. Consequently, t (n) = t (Ln/2 ˩) + t (ᴦn/2Ꞁ) + g(n) where g(n) = θ (n). This recurrence becomes t (n) = 2t (n/2) + g (n) when n is even. Now using master theorem, the running time becomes t (n) = θ (n log n).


For more detail analysis of the algorithm, please refer to CLRS book on Introduction to Algorithms.


For Insertion sort, please visit https://selfstudygeek.blogspot.com/2018/11/whatis-sorting-supposeyou-are-playing.html

Comments

Post a Comment

Popular posts from this blog

Binary Search

Image
Binary search is used to locate an element in an array efficiently than the linear search. To use a binary search, the array must be sorted in non-decreasing order. If T[1…n] is the sorted array, then the binary search returns an index i at which the element(say x) is found. If the element is not in the array then, it returns a possible index where the element might be inserted. Here, we wish to find the index i such that 1 < i < n + 1 and T[i - 1] < x < T[i]. At first, let’s see how do we locate an element in an array using linear or sequential approach. LINEAR-SEARCH (T[1…n], x) for i = 1 to n if T[i] > x return i return n + 1 From the above algorithm, we can see clearly that the algorithm takes the time in θ(n) in the worst case where n is the number of elements. Now, let’s see how binary search algorithm will improve this running time. Basically, a binary search algorithm works like this. First, we compare the element x with the middle element of...
Read more

System Bus

Image
Have you ever wondered how the microprocessor communicates with the devices connected to it? Well, there are a group of wires (communication path) between microprocessor and its peripherals (and memory) to carry bits which are known as system bus. The system bus performs the following steps to communicate with the peripheral: i.         Identify the peripheral or the memory location (with its address). ii.       Transfer data and instructions in the form of bits. iii.     Provide timing and synchronization signals. According to the above functions, system bus can be classified into three types which are described below: Address Bus: It is a set of wires that is used to transmit address from the microprocessor to its peripheral devices (or memory. It is unidirectional. Each peripheral or memory is identified by its address. This is similar to the postal address of the house. For example...
Read more

Differences between hardwired and micro-programmed control unit

S.N. Hardwired Control Unit Micro-programmed Control Unit 1. It is implemented through the use of sequential logic circuit. Its input logic signals are transformed into a set of output logic signals which are control signals. It is implemented through the use of micro-programs. Micro-programs (control information) are organized as a sequence of micro-instructions stored in a special control memory. 2. This design uses a fixed architecture so, it require changes in wiring if the instruction set is modified. It is easy to reconfigure and modify instruction set. 3. It is difficult to build a circuit that satisfies all the operations. It is simple in structure. 4. It has faster mode of operation. It is comparatively slower. 5. It is comparatively expensive. It is cheaper. 6. It is preferred for less number of instruction sets. I...
Read more