Merge Sort

Merge sort is a sorting algorithm that uses the divide, conquer, and combine algorithmic paradigm. The running time of merge sort in the average case and the worst case can be given as O(n log n).

Divide means partitioning the n-element array to be sorted into two sub-arrays of n/2 elements. If A is an array containing zero or one element, then it is already sorted. However, if there are more elements in the array, divide A into two sub-arrays, A1 and A2, each containing about half of the elements of A.

Conquer means sorting the two sub-arrays recursively using merge sort.

Combine means merging the two sorted sub-arrays of size n/2 to produce the sorted array of n elements.

Merge sort algorithm focuses on two main concepts to improve its performance (running time):

A smaller list takes fewer steps and thus less time to sort than a large list.
As number of steps is relatively less, thus less time is needed to create a sorted list from two sorted lists rather than creating it using two unsorted lists.

Procedure

The basic steps of an algorithm are as follows:

If the array is of length 0 or 1, then it is already sorted.
Otherwise, divide the unsorted array into two sub-arrays of about half the size.
Use merge sort algorithm recursively to sort each sub-array.
Merge the two sub-arrays to form a single sorted list.

Example : Sort the array given below using merge sort.

Merge Sort Example

The sorting algorithm uses a function merge which combines the sub-arrays to form a sorted array. While the merge sort algorithm recursively divides the list into smaller lists, the merge algorithm conquers the list to sort the elements in individual lists. Finally, the smaller lists are merged to form one list.

To understand the merge algorithm, consider the figure below which shows how we merge two lists to form one list. For ease of understanding, we have taken two sub-lists each containing four elements. The same concept can be utilized to merge four sub-lists containing two elements, or eight sub-lists having one element each.

Merge Sort Data Structure

Compare ARR[I] and ARR[J], the smaller of the two is placed in TEMP at the location specified by INDEX and subsequently the value I or J is incremented.

Algorithm Tracing

When I is greater than MID, copy the remaining elements of the right sub-array in TEMP.

Algorithm Explanation

Merge Sort Algorithm

Copy to Clipboard

MERGE (ARR, BEG, MID, END)

Step 1: [INITIALIZE] 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: END

Related Topic:
C Program to implement Merge Sort Algorithm

<< Prev – Quick Sort