Merge Sort program in the data structure

Data Structure Sorting (Article) Sorting (Program)

880

Program:

<span class="com">/*  
    a[] is the array, p is starting index, that is 0, 
    and r is the last index of array. 
*/</span><span class="pln">

</span><span class="com">#include</span><span class="pln"> </span><span class="str">&lt;stdio.h&gt;</span><span class="pln">

</span><span class="com">// lets take a[5] = {32, 45, 67, 2, 7} as the array to be sorted.</span><span class="pln">

</span><span class="com">// merge sort function</span><span class="pln">
</span><span class="kwd">void</span><span class="pln"> mergeSort</span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> a</span><span class="pun">[],</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> p</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> r</span><span class="pun">)</span><span class="pln">
</span><span class="pun">{</span><span class="pln">
    </span><span class="kwd">int</span><span class="pln"> q</span><span class="pun">;</span><span class="pln">
    </span><span class="kwd">if</span><span class="pun">(</span><span class="pln">p </span><span class="pun">&lt;</span><span class="pln"> r</span><span class="pun">)</span><span class="pln">
    </span><span class="pun">{</span><span class="pln">
        q </span><span class="pun">=</span><span class="pln"> </span><span class="pun">(</span><span class="pln">p </span><span class="pun">+</span><span class="pln"> r</span><span class="pun">)</span><span class="pln"> </span><span class="pun">/</span><span class="pln"> </span><span class="lit">2</span><span class="pun">;</span><span class="pln">
        mergeSort</span><span class="pun">(</span><span class="pln">a</span><span class="pun">,</span><span class="pln"> p</span><span class="pun">,</span><span class="pln"> q</span><span class="pun">);</span><span class="pln">
        mergeSort</span><span class="pun">(</span><span class="pln">a</span><span class="pun">,</span><span class="pln"> q</span><span class="pun">+</span><span class="lit">1</span><span class="pun">,</span><span class="pln"> r</span><span class="pun">);</span><span class="pln">
        merge</span><span class="pun">(</span><span class="pln">a</span><span class="pun">,</span><span class="pln"> p</span><span class="pun">,</span><span class="pln"> q</span><span class="pun">,</span><span class="pln"> r</span><span class="pun">);</span><span class="pln">
    </span><span class="pun">}</span><span class="pln">
</span><span class="pun">}</span><span class="pln">

</span><span class="com">// function to merge the subarrays</span><span class="pln">
</span><span class="kwd">void</span><span class="pln"> merge</span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> a</span><span class="pun">[],</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> p</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> q</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> r</span><span class="pun">)</span><span class="pln">
</span><span class="pun">{</span><span class="pln">
    </span><span class="kwd">int</span><span class="pln"> b</span><span class="pun">[</span><span class="lit">5</span><span class="pun">];</span><span class="pln">   </span><span class="com">//same size of a[]</span><span class="pln">
    </span><span class="kwd">int</span><span class="pln"> i</span><span class="pun">,</span><span class="pln"> j</span><span class="pun">,</span><span class="pln"> k</span><span class="pun">;</span><span class="pln">
    k </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln">
    i </span><span class="pun">=</span><span class="pln"> p</span><span class="pun">;</span><span class="pln">
    j </span><span class="pun">=</span><span class="pln"> q </span><span class="pun">+</span><span class="pln"> </span><span class="lit">1</span><span class="pun">;</span><span class="pln">
    </span><span class="kwd">while</span><span class="pun">(</span><span class="pln">i </span><span class="pun">&lt;=</span><span class="pln"> q </span><span class="pun">&amp;&amp;</span><span class="pln"> j </span><span class="pun">&lt;=</span><span class="pln"> r</span><span class="pun">)</span><span class="pln">
    </span><span class="pun">{</span><span class="pln">
        </span><span class="kwd">if</span><span class="pun">(</span><span class="pln">a</span><span class="pun">[</span><span class="pln">i</span><span class="pun">]</span><span class="pln"> </span><span class="pun">&lt;</span><span class="pln"> a</span><span class="pun">[</span><span class="pln">j</span><span class="pun">])</span><span class="pln">
        </span><span class="pun">{</span><span class="pln">
            b</span><span class="pun">[</span><span class="pln">k</span><span class="pun">++]</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> a</span><span class="pun">[</span><span class="pln">i</span><span class="pun">++];</span><span class="pln">    </span><span class="com">// same as b[k]=a[i]; k++; i++;</span><span class="pln">
        </span><span class="pun">}</span><span class="pln">
        </span><span class="kwd">else</span><span class="pln">
        </span><span class="pun">{</span><span class="pln">
            b</span><span class="pun">[</span><span class="pln">k</span><span class="pun">++]</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> a</span><span class="pun">[</span><span class="pln">j</span><span class="pun">++];</span><span class="pln">
        </span><span class="pun">}</span><span class="pln">
    </span><span class="pun">}</span><span class="pln">
  
    </span><span class="kwd">while</span><span class="pun">(</span><span class="pln">i </span><span class="pun">&lt;=</span><span class="pln"> q</span><span class="pun">)</span><span class="pln">
    </span><span class="pun">{</span><span class="pln">
        b</span><span class="pun">[</span><span class="pln">k</span><span class="pun">++]</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> a</span><span class="pun">[</span><span class="pln">i</span><span class="pun">++];</span><span class="pln">
    </span><span class="pun">}</span><span class="pln">
  
    </span><span class="kwd">while</span><span class="pun">(</span><span class="pln">j </span><span class="pun">&lt;=</span><span class="pln"> r</span><span class="pun">)</span><span class="pln">
    </span><span class="pun">{</span><span class="pln">
        b</span><span class="pun">[</span><span class="pln">k</span><span class="pun">++]</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> a</span><span class="pun">[</span><span class="pln">j</span><span class="pun">++];</span><span class="pln">
    </span><span class="pun">}</span><span class="pln">
  
    </span><span class="kwd">for</span><span class="pun">(</span><span class="pln">i</span><span class="pun">=</span><span class="pln">r</span><span class="pun">;</span><span class="pln"> i </span><span class="pun">&gt;=</span><span class="pln"> p</span><span class="pun">;</span><span class="pln"> i</span><span class="pun">--)</span><span class="pln">
    </span><span class="pun">{</span><span class="pln">
        a</span><span class="pun">[</span><span class="pln">i</span><span class="pun">]</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> b</span><span class="pun">[--</span><span class="pln">k</span><span class="pun">];</span><span class="pln">  </span><span class="com">// copying back the sorted list to a[]</span><span class="pln">
    </span><span class="pun">}</span><span class="pln"> 
</span><span class="pun">}</span><span class="pln">

</span><span class="com">// function to print the array</span><span class="pln">
</span><span class="kwd">void</span><span class="pln"> printArray</span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> a</span><span class="pun">[],</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> size</span><span class="pun">)</span><span class="pln">
</span><span class="pun">{</span><span class="pln">
    </span><span class="kwd">int</span><span class="pln"> i</span><span class="pun">;</span><span class="pln">
    </span><span class="kwd">for</span><span class="pln"> </span><span class="pun">(</span><span class="pln">i</span><span class="pun">=</span><span class="lit">0</span><span class="pun">;</span><span class="pln"> i </span><span class="pun">&lt;</span><span class="pln"> size</span><span class="pun">;</span><span class="pln"> i</span><span class="pun">++)</span><span class="pln">
    </span><span class="pun">{</span><span class="pln">
        printf</span><span class="pun">(</span><span class="str">"%d "</span><span class="pun">,</span><span class="pln"> a</span><span class="pun">[</span><span class="pln">i</span><span class="pun">]);</span><span class="pln">
    </span><span class="pun">}</span><span class="pln">
    printf</span><span class="pun">(</span><span class="str">"\n"</span><span class="pun">);</span><span class="pln">
</span><span class="pun">}</span><span class="pln">
 
</span><span class="kwd">int</span><span class="pln"> main</span><span class="pun">()</span><span class="pln">
</span><span class="pun">{</span><span class="pln">
    </span><span class="kwd">int</span><span class="pln"> arr</span><span class="pun">[]</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> </span><span class="pun">{</span><span class="lit">32</span><span class="pun">,</span><span class="pln"> </span><span class="lit">45</span><span class="pun">,</span><span class="pln"> </span><span class="lit">67</span><span class="pun">,</span><span class="pln"> </span><span class="lit">2</span><span class="pun">,</span><span class="pln"> </span><span class="lit">7</span><span class="pun">};</span><span class="pln">
    </span><span class="kwd">int</span><span class="pln"> len </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">sizeof</span><span class="pun">(</span><span class="pln">arr</span><span class="pun">)/</span><span class="kwd">sizeof</span><span class="pun">(</span><span class="pln">arr</span><span class="pun">[</span><span class="lit">0</span><span class="pun">]);</span><span class="pln">
 
    printf</span><span class="pun">(</span><span class="str">"Given array: \n"</span><span class="pun">);</span><span class="pln">
    printArray</span><span class="pun">(</span><span class="pln">arr</span><span class="pun">,</span><span class="pln"> len</span><span class="pun">);</span><span class="pln">
    
    </span><span class="com">// calling merge sort</span><span class="pln">
    mergeSort</span><span class="pun">(</span><span class="pln">arr</span><span class="pun">,</span><span class="pln"> </span><span class="lit">0</span><span class="pun">,</span><span class="pln"> len </span><span class="pun">-</span><span class="pln"> </span><span class="lit">1</span><span class="pun">);</span><span class="pln">
 
    printf</span><span class="pun">(</span><span class="str">"\nSorted array: \n"</span><span class="pun">);</span><span class="pln">
    printArray</span><span class="pun">(</span><span class="pln">arr</span><span class="pun">,</span><span class="pln"> len</span><span class="pun">);</span><span class="pln">
    </span><span class="kwd">return</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln">
</span><span class="pun">}</span>

Output:

Given array:
32 45 67 2 7
Sorted array:
2 7 32 45 67

Explanation:

Merge Sort follows the rule of Divide and Conquer to sort a given set of numbers/elements, recursively, hence consuming less time.

In the last two tutorials, we learned about Selection Sort and Insertion Sort, both of which have a worst-case running time of O(n2). As the size of input grows, insertion and selection sort can take a long time to run.

Merge sort , on the other hand, runs in O(n*log n) time in all the cases.

Before jumping on to, how merge sort works and it's implementation, first lets understand what is the rule of Divide and Conquer?

This Particular section is dedicated to Programs only. If you want learn more about Data Structure. Then you can visit below links to get more depth on this subject.