Goseeko blog

What is Merge sort?

by Bhumika

Merge Sort is based on a divide and conquer strategy. It divides the unsorted list into n sublists such that each sublist contains one element. Each sublist is then sorted and merged until there is only one sublist. 

 Step1 : Divide the list into sublists such that each sublist contains only one element.

 Step2 : Sort each sublist and Merge them.

 Step3 : Repeat Step 2 till the entire list is sorted. 

Algorithm for Merge Sort:

 Let    x = no. of elements in array A

    y = no. of elements in array B

    C = sorted array with no. of elements n

    n = x+y

Following algorithm merges a sorted x element array A and sorted y element array B into a sorted array C, with n = x + y elements. We must always keep track of the locations of the smallest element of A and the smallest element of B which have not yet been placed in C. Let LA and LB denote these locations, respectively. Also, let LC denote the location in C to be filled. Thus, initially, we set 

 LA : = 1, 

 LB : = 1 and 

 LC : = 1. 

 At each step , we compare A[LA] and B[LB] and assign the smaller element to C[LC]. 


 LC:= LC + 1,

 LA: = LA + 1, if a new element has come from A . 

 LB: = LB + 1, if a new element has come from B. 

 Furthermore, if LA> x, then the remaining elements of B are assigned to C;  

  LB >y, then the remaining elements of A are assigned to C. 

Thus the algorithm becomes

 MERGING ( A, x, B, y, C)

 1. [Initialize ] Set LA : = 1 , LB := 1 AND LC : = 1

 2. [Compare] Repeat while LA <= x and LB <= y

 If A[LA] < B[LB] , then

 (a) [Assign element from A to C ] set C[LC] = A[LA]

 (b) [Update pointers ] Set LC := LC +1 and LA = LA+1


 (a) [Assign element from B to C] Set C[LC] = B[LB]

 (b) [Update Pointers] Set LC := LC +1 and LB = LB +1

 [End of loop]

 3. [Assign remaining elements to C]

 If LA > x , then

 Repeat for K= 0 ,1,2,……..,y–LB

 Set C[LC+K] = B[LB+K]

 [End of loop]


 Repeat for K = 0,1,2,……,x–LA

 Set C[LC+K] = A[LA+K]

 [End of loop]

 4. Exit

Interested in learning about similar topics? Here are a few hand-picked blogs for you!

  1. What is data structure?
  2. Explain computer processor?
  3. What is Memory?
  4. What is Computer?

You may also like