Merge sort

Merge sort is based on the divide & conquer sorting technique. Merge sort is a very efficient sorting algorithm. The divide & conquer technique was introduced by John Newman in 1945. The divide & conquer is a technique in which a complex list of data is divided into a sub-list, and this list is split until there is only one element left in the list. After that, these sub-lists are sorted, and then all elements are combined. Merge sort is also called a two-way sort.

Complexity table of Merge sort

ComplexityBest caseAverage caseWorst case
TimeO(nlogn)O(nlogn)O(nlogn)
Space  O(n)

Merge sort algorithm

Step 1: MERGE (SET I = BEG, J = MID + 1, INDEX = 0)
Step 2: Repeat while (I <= MID) and (J<=END)
             if ARR[I] < ARR[J]
             SET TEMP[INDEX] = ARR[I]
             SET I = I + 1
             else
             SET TEMP[INDEX] = ARR[J]
             SET J = J + 1
             //end of if
             SET INDEX = INDEX + 1
             //end of loop
Step 3: [Copy the remaining elements of right sub-array, if any]
            if I > MID
            Repeat while J <= END
            SET TEMP[INDEX] = ARR[J]
            SET INDEX = INDEX + 1, SET J = J + 1
            //end of loop
            [Copy the remaining elements of left sub-array, if any]
                        else
            Repeat while I <= MID
            SET TEMP[INDEX] = ARR[I]
            SET INDEX = INDEX + 1, SET I = I + 1
            //end of loop
            //end of if
Step 4: [Copy the contents of TEMP back to ARR] SET K = 0
Step 5: Repeat while K < INDEX
             SET ARR[K] = TEMP[K]
             SET K = K + 1
             //end of loop
Step 6: exit  

Merge sort example

Suppose we have the following array, which we have to sort.

1154456532449125

As you know, the whole array is divided into two parts in the merge sort.

This array has 8 elements, and this array will be divided into two arrays. You divide this array until there is only one element remain in it. After this, all elements are compared with each other, and after that, they are sorted and combined.

Merge sort

Merge sort program in C language

Output:

Pin It on Pinterest

Share This