{"id":5361,"date":"2021-10-07T02:18:06","date_gmt":"2021-10-07T02:18:06","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=5361"},"modified":"2023-07-27T12:22:24","modified_gmt":"2023-07-27T12:22:24","slug":"c-program-for-merge-sort-for-linked-lists","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/","title":{"rendered":"C Program For Merge Sort For Linked Lists"},"content":{"rendered":"<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645011665100-Article_188.png\" alt=\"\" \/><\/p>\n<h3>Introduction<\/h3>\n<p>This blog post will guide you through implementing merge sort using linked lists in C. Sorting is a fundamental aspect of data structures. Before delving into the details of merge sort, let&#8217;s first grasp the basic concepts involved..<\/p>\n<h3>Problem Statement of merge sort using a linked list in C<\/h3>\n<p>According to the problem statement, we are given a singly linked list, and we need to sort this singly linked list using merge sort.<\/p>\n<h3>What is Merge Sort in C Language<\/h3>\n<p>Merge sort is a divide and conquer algorithm. <\/p>\n<ul>\n<li>It is a recursive algorithm. <\/li>\n<li>In merge sort, we have to divide the container (container can be an array, list, etc.) into two halves, then we will call merge sort recursively on the two halves. <\/li>\n<li>These two merge sort calls return a sorted container, and we then merge these sorted containers in such a way that the whole container remains sorted.<\/li>\n<li>Have a look at the below image to see in a nutshell how merge sort works.\n<\/li>\n<\/ul>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_1-40.png\" alt=\"\" \/><\/p>\n<p>Now, we have a brief understanding of the merge sort algorithm. Let\u2019s learn how to apply merge sort on a singly linked list.<\/p>\n<p>In the case of a linked list, we will recursively divide the list into two sub-lists at each step till the list size is reduced to one and while backtracking from the recursive call, we have two sorted lists, which will be merged together into a single list by merge operation in linear time.<\/p>\n<p>Now we will look at the approach and algorithm, to know how to apply merge sort on a singly linked list.<\/p>\n<h3>Approach and Algorithm of merge sort using a linked list in C<\/h3>\n<ol>\n<li>If the <strong>head<\/strong> of the linked list is NULL or <strong>(head\u2192 next == NULL)<\/strong>, it shows that our linked list is of size 1 or 0 and a linked list of size zero or one is already sorted. So, Don\u2019t do anything, just return <strong>head<\/strong>.<\/li>\n<li>If the linked list is of <strong>size &gt; 1<\/strong> then first find the <strong>middle<\/strong> of the linked list. <\/li>\n<ul>\n<li>For finding middle node, use <strong>slow and fast pointer method<\/strong>. <\/li>\n<li>In this method, we take two pointers <strong>slow<\/strong> and <strong>fast<\/strong> and initialize them with <strong>head<\/strong>. <\/li>\n<li>Then we move the <strong>slow pointer<\/strong> by one node and <strong>fast pointer<\/strong> by 2 nodes until the fast pointer reaches the tail of the list. <\/li>\n<li>And when the <strong>fast pointer<\/strong> reaches the <strong>tail<\/strong>, the <strong>slow pointer<\/strong> will be at the <strong>middle<\/strong> of the linked list.<\/li>\n<li>The only reason why <strong>slow pointer<\/strong> will be at the <strong>middle<\/strong> of the list, when <strong>fast<\/strong> reaches <strong>tail<\/strong> is because the <strong>slow pointer is moving with half the speed of fast pointer<\/strong> and when the fast pointer has traversed the complete list till then the slow pointer will have only traversed half the list, so that\u2019s why slow pointer will be at the middle of the list.<\/li>\n<\/ul>\n<li>Now, store <strong>slow \u2192 next<\/strong> in a pointer named <strong>afterMiddle<\/strong> and assign <strong>slow \u2192 next = NULL<\/strong>.<\/li>\n<li>Recursively call <strong>mergeSort()<\/strong> on both <strong>left and right sub-linked list<\/strong> and store the new head of the left and right linked list in pointer variable <strong>part1<\/strong> and <strong>part2<\/strong>.<\/li>\n<li>When the recursive call on the left and right sub-list returns, merge the two linked lists returned by recursive calls (remember that the recursive call will return the sorted lists).<\/li>\n<li>Return the final head of the merged linked list.<\/li>\n<\/ol>\n<h4>Merging two sorted linked list Algorithm:<\/h4>\n<p>When the two recursive calls will return the two sorted lists, then we will merge that sorted list into a single list using these below steps.<\/p>\n<ol>\n<li>Initialize two pointer variables named <strong>curr1<\/strong> and <strong>curr2<\/strong> with left sorted sub-list and right sorted sub-list.<\/li>\n<li>Initialize two pointer variable named <strong>si<\/strong> and <strong>ei<\/strong> with NULL; these two pointer variables are the <strong>head<\/strong> and <strong>tail<\/strong> of the final sorted linked list.<\/li>\n<li>If the data of <strong>curr1<\/strong> is less than the data of <strong>curr2<\/strong>, then, store <strong>curr1<\/strong> in next of <strong>ei<\/strong> &amp; move <strong>curr1<\/strong> to the next of <strong>curr1<\/strong>.<\/li>\n<li>Else, if the data of <strong>curr2<\/strong> is less than the data of <strong>curr1<\/strong>, then store <strong>curr2<\/strong> in next of <strong>ei<\/strong> &amp; move <strong>curr2<\/strong> to the next of <strong>curr2<\/strong>.<\/li>\n<li>Repeat steps 3 and 4 until either of the <strong>curr1<\/strong> or <strong>curr2<\/strong> is not equal to NULL.<\/li>\n<li>Now add any remaining nodes of the first or the second linked list to the merged linked list.<\/li>\n<li>Return the head of the merged sorted linked list containing all the nodes of the two sorted sub-lists.<\/li>\n<\/ol>\n<h3>Dry Run of merge sort using a linked list in C<\/h3>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_2-39.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_3-24.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_4-15.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_5-10.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_6-10.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_7-9.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_8-9.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_9-5.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_10-3.png\" alt=\"\" \/><\/p>\n<h3>Code Implementation of merge sort using a linked list in C<\/h3>\n\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_5362 {\r\n\toverflow:hidden;\r\n\tdisplay:block;\r\n\twidth:100%;\r\n\tborder:0px solid #ddd;\r\n\tmargin-bottom:30px;\r\n\t}\r\n\r\n#tab_container_5362 .tab-content{\r\n\tpadding:20px;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n\tmargin-top: 0px;\r\n\tbackground-color:#ffffff !important;\r\n\tcolor: #000000 !important;\r\n\tfont-size:16px !important;\r\n\tfont-family: Open Sans !important;\r\n\t\r\n\t\tborder: 1px solid #e6e6e6 !important;\r\n\t}\r\n#tab_container_5362 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_5362 .wpsm_nav-tabs > li.active > a, #tab_container_5362 .wpsm_nav-tabs > li.active > a:hover, #tab_container_5362 .wpsm_nav-tabs > li.active > a:focus {\r\n\tcolor: #000000 !important;\r\n\tcursor: default;\r\n\tbackground-color: #ffffff !important;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n}\r\n\r\n#tab_container_5362 .wpsm_nav-tabs > li > a {\r\n    margin-right: 0px !important; \r\n    line-height: 1.42857143 !important;\r\n    border: 1px solid #d5d5d5 !important;\r\n    border-radius: 0px 0px 0 0 !important; \r\n\tbackground-color: #e8e8e8 !important;\r\n\tcolor: #000000 !important;\r\n\tpadding: 15px 18px 15px 18px !important;\r\n\ttext-decoration: none !important;\r\n\tfont-size: 14px !important;\r\n\ttext-align:center !important;\r\n\tfont-family: Open Sans !important;\r\n}\r\n#tab_container_5362 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_5362 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_5362 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_5362 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_5362 .wpsm_nav-tabs > li > a:hover , #tab_container_5362 .wpsm_nav-tabs > li > a:focus {\r\n    color: #000000 !important;\r\n    background-color: #e8e8e8 !important;\r\n\tborder: 1px solid #d5d5d5 !important;\r\n\t\r\n}\r\n#tab_container_5362 .wpsm_nav-tabs > li > a .fa{\r\n\r\nmargin-right:5px !important;\r\n\r\nmargin-left:5px !important;\r\n\r\n\r\n}\r\n\r\n\t\t#tab_container_5362 .wpsm_nav-tabs a{\r\n\t\t\tbackground-image: none;\r\n\t\t\tbackground-position: 0 0;\r\n\t\t\tbackground-repeat: repeat-x;\r\n\t\t}\r\n\t\t\t\r\n\r\n\r\n#tab_container_5362 .wpsm_nav-tabs > li {\r\n    float: left;\r\n    margin-bottom: -1px !important;\r\n\tmargin-right:0px !important; \r\n}\r\n\r\n\r\n#tab_container_5362 .tab-content{\r\noverflow:hidden !important;\r\n}\r\n\r\n\r\n@media (min-width: 769px) {\r\n\r\n\t#tab_container_5362 .wpsm_nav-tabs > li{\r\n\t\tfloat:left !important ;\r\n\t\t\t\tmargin-right:-1px !important;\r\n\t\t\t\t\t}\r\n\t#tab_container_5362 .wpsm_nav-tabs{\r\n\t\tfloat:none !important;\r\n\t\tmargin:0px !important;\r\n\t}\r\n\r\n\t#tab_container_5362 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_5362 .wpsm_nav{\r\n\t\t\t}\r\n\r\n}\r\n\r\n\r\n\r\n@media (max-width: 768px) {\r\n\t#tab_container_5362 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_5362 .wpsm_nav{\r\n\t\t\t}\r\n}\r\n\r\n\r\n\t.wpsm_nav-tabs li:before{\r\n\t\tdisplay:none !important;\r\n\t}\r\n\r\n\t@media (max-width: 768px) {\r\n\t\t\t\t\r\n\t\t\t\t.wpsm_nav-tabs{\r\n\t\t\tmargin-left:0px !important;\r\n\t\t\tmargin-right:0px !important; \r\n\t\t\t\r\n\t\t}\r\n\t\t\t\t#tab_container_5362 .wpsm_nav-tabs > li{\r\n\t\t\tfloat:none !important;\r\n\t\t}\r\n\t\t\t\r\n\t}\t\t\t\t<\/style>\r\n\t\t\t\t<div id=\"tab_container_5362\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_5362\">\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  class=\"active\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_5362_1\" aria-controls=\"tabs_desc_5362_1\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>C<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\t\t\t\t <\/ul>\r\n\r\n\t\t\t\t\t  <!-- Tab panes -->\r\n\t\t\t\t\t  <div class=\"tab-content\" id=\"tab-content_5362\">\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane  in active \" id=\"tabs_desc_5362_1\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"c\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"c\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\n#include <stdio.h>\r\n#include <stdlib.h>\r\n\r\n\/* Link list node *\/\r\nstruct Node {\r\n    int data;\r\n    struct Node* next;\r\n};\r\n\r\n\/* function prototypes *\/\r\nstruct Node* SortedMerge(struct Node* a, struct Node* b);\r\nvoid middle(struct Node* source,\r\n                    struct Node** frontRef, struct Node** backRef);\r\n\r\n\/* sorts the linked list by changing links *\/\r\nvoid MergeSort(struct Node** headRef){\r\n    struct Node* head = *headRef;\r\n    struct Node* a;\r\n    struct Node* b;\r\n\r\n    \/* Base case -- length 0 or 1 *\/\r\n    if ((head == NULL) || (head->next == NULL)) {\r\n        return;\r\n    }\r\n\r\n    middle(head, &a, &b);\r\n\r\n    MergeSort(&a);\r\n    MergeSort(&b);\r\n\r\n    *headRef = SortedMerge(a, b);\r\n}\r\n\r\nstruct Node* SortedMerge(struct Node* a, struct Node* b)\r\n{\r\n    struct Node* result = NULL;\r\n\r\n    \/* Base cases *\/\r\n    if (a == NULL)\r\n        return (b);\r\n    else if (b == NULL)\r\n        return (a);\r\n\r\n    if (a->data <= b->data) {\r\n        result = a;\r\n        result->next = SortedMerge(a->next, b);\r\n    }\r\n    else {\r\n        result = b;\r\n        result->next = SortedMerge(a, b->next);\r\n    }\r\n    return (result);\r\n}\r\n\r\n\/* This function splits the list from the middle *\/\r\n\/* After splitting Original list converts into two list \r\n   first list -> head to the node previous of middle and second list -> middle to end *\/\r\n\r\nvoid middle(struct Node* source,\r\n                    struct Node** frontRef, struct Node** backRef)\r\n{\r\n    struct Node* fast;\r\n    struct Node* slow;\r\n    slow = source;\r\n    fast = source->next;\r\n\r\n    \/* Advance 'fast' two nodes, and advance 'slow' one node *\/\r\n    while (fast != NULL) {\r\n        fast = fast->next;\r\n        if (fast != NULL) {\r\n            slow = slow->next;\r\n            fast = fast->next;\r\n        }\r\n    }\r\n\r\n    \/* 'slow' is before the midpoint in the list, so split it in two\r\n    at that point. *\/\r\n    *frontRef = source;\r\n    *backRef = slow->next;\r\n    slow->next = NULL;\r\n}\r\n\r\n\/* Function to print linked list *\/\r\nvoid printList(struct Node* node){\r\n    while (node != NULL) {\r\n        printf(\"%d \", node->data);\r\n        node = node->next;\r\n    }\r\n}\r\n\r\n\/* Function to insert a node at the beginning of the list *\/\r\nvoid push(struct Node** head_ref, int new_data){\r\n    \/* allocate node *\/\r\n    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));\r\n\r\n    \/* assign the data *\/\r\n    new_node->data = new_data;\r\n\r\n    \/* link the old list off the new node *\/\r\n    new_node->next = (*head_ref);\r\n\r\n    \/* move the head pointer to point to the new node *\/\r\n    (*head_ref) = new_node;\r\n}\r\n\r\nint main(){\r\n    \r\n    struct Node* res = NULL;\r\n    struct Node* a = NULL;\r\n\r\n    \/* Let's create a new linked lists *\/\r\n   \/* a: 8->9->5->3->2 *\/\r\n    push(&a, 2);\r\n    push(&a, 3);\r\n    push(&a, 5);\r\n    push(&a, 9);\r\n    push(&a, 8);\r\n    \r\n    printf(\"Linked List before sorting: &#92;n\");\r\n    printList(a);\r\n    printf(\"&#92;n\");\r\n    \/* Sort the Linked List *\/\r\n    MergeSort(&a);\r\n    printf(\"Linked List after Sorting: &#92;n\");\r\n    printList(a);\r\n\r\n    getchar();\r\n    return 0;\r\n}\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t <\/div>\r\n\t\t\t\t\t \r\n\t\t\t\t <\/div>\r\n <script>\r\n\t\tjQuery(function () {\r\n\t\t\tjQuery('#myTab_5362 a:first').tab('show')\r\n\t\t});\r\n\t\t\r\n\t\t\t\tjQuery(function(){\r\n\t\t\tvar b=\"fadeIn\";\r\n\t\t\tvar c;\r\n\t\t\tvar a;\r\n\t\t\td(jQuery(\"#myTab_5362 a\"),jQuery(\"#tab-content_5362\"));function d(e,f,g){\r\n\t\t\t\te.click(function(i){\r\n\t\t\t\t\ti.preventDefault();\r\n\t\t\t\t\tjQuery(this).tab(\"show\");\r\n\t\t\t\t\tvar h=jQuery(this).data(\"easein\");\r\n\t\t\t\t\tif(c){c.removeClass(a);}\r\n\t\t\t\t\tif(h){f.find(\"div.active\").addClass(\"animated \"+h);a=h;}\r\n\t\t\t\t\telse{if(g){f.find(\"div.active\").addClass(\"animated \"+g);a=g;}else{f.find(\"div.active\").addClass(\"animated \"+b);a=b;}}c=f.find(\"div.active\");\r\n\t\t\t\t});\r\n\t\t\t}\r\n\t\t});\r\n\t\t\r\n\r\n\t\tfunction do_resize(){\r\n\r\n\t\t\tvar width=jQuery( '.tab-content .tab-pane iframe' ).width();\r\n\t\t\tvar height=jQuery( '.tab-content .tab-pane iframe' ).height();\r\n\r\n\t\t\tvar toggleSize = true;\r\n\t\t\tjQuery('iframe').animate({\r\n\t\t\t    width: toggleSize ? width : 640,\r\n\t\t\t    height: toggleSize ? height : 360\r\n\t\t\t  }, 250);\r\n\r\n\t\t\t  toggleSize = !toggleSize;\r\n\t\t}\r\n\r\n\r\n\t<\/script>\r\n\t\t\t\t\r\n\t\t\t\n<h4>Output<\/h4>\n<p>Linked List before sorting<br \/>\n8 9 5 3 2<br \/>\nLinked List after sorting<br \/>\n2 3 5 8 9 <\/p>\n<p><strong>Time Complexity of merge sort using a linked list in C:<\/strong> O(n*log n)<\/p>\n<p>So, In this article, we have learned how to apply for the merge sort <a href=\"https:\/\/prepbytes.com\/blog\/c-programming\/basic-c-programs-examples\/\"><br \/>\nprogram in C<\/a>. We discussed the merge sort algorithm in detail we also took a look at the time and space complexity of merge sort for linked list in detail. This is an important problem when it comes to coding interviews. If you want to practice more questions on linked lists feel free to solve them at <a href=\"https:\/\/mycode.prepbytes.com\/interview-coding\/practice\/linked-list\">Prepbytes (Linked Lists)<\/a>.<\/p>\n<h2>FAQs related to merge sort using linked list in C<\/h2>\n<p><strong>Q1. What is merge sort, and how does it work with linked lists in C?<\/strong><br \/>\nMerge sort is a popular sorting algorithm that employs the divide-and-conquer technique. It works with linked lists by recursively dividing the list into smaller sublists, sorting each sublist individually, and then merging them back together to obtain the sorted output.<\/p>\n<p><strong>Q2. Why is merge sort a preferred sorting algorithm for linked lists?<\/strong><br \/>\nMerge sort is preferred for linked lists because it has a stable time complexity of O(n log n) and doesn&#8217;t require random access, which is advantageous for linked lists where direct access to elements is inefficient.<\/p>\n<p><strong>Q3. What are the time and space complexities of merge sort for linked lists in C?<\/strong><br \/>\nThe time complexity of merge sort for linked lists is O(n log n), where n is the number of elements in the list. The space complexity is O(log n) due to the recursive nature of the algorithm.<\/p>\n<p><strong>Q4. Can merge sort be used for sorting large linked lists efficiently?<\/strong><br \/>\nYes, merge sort is efficient for sorting large linked lists due to its O(n log n) time complexity. It divides the sorting process into smaller parts, making it manageable for larger datasets.<\/p>\n<p><strong>Other C Programs<\/strong><br \/>\n<a href=\"https:\/\/prepbytes.com\/blog\/c-programming\/c-program-to-calculate-percentage-of-5-subjects\/\">C program to calculate percentage of 5 subjects<\/a><br \/>\n<a href=\"https:\/\/prepbytes.com\/blog\/c-programming\/c-program-to-convert-binary-number-to-decimal-number\/\">C program to convert binary number to decimal number<\/a><br \/>\n<a href=\"https:\/\/prepbytes.com\/blog\/c-programming\/c-program-to-convert-celsius-to-fahrenheit\/\">C program to convert celsius to fahrenheit<\/a><br \/>\n<a href=\"https:\/\/prepbytes.com\/blog\/c-programming\/c-program-to-convert-infix-to-postfix\/\">C program to convert infix to postfix<\/a><br \/>\n<a href=\"https:\/\/prepbytes.com\/blog\/c-programming\/c-program-to-find-area-of-circle\/\">C program to find area of circle<\/a><br \/>\n<a href=\"https:\/\/prepbytes.com\/blog\/c-programming\/c-program-to-find-roots-of-quadratic-equation\/\">C program to find roots of quadratic equation<\/a><br \/>\n<a href=\"https:\/\/prepbytes.com\/blog\/c-programming\/c-program-to-reverse-a-number\/\">C program to reverse a number<\/a><br \/>\n<a href=\"https:\/\/prepbytes.com\/blog\/c-programming\/c-program-to-add-two-numbers\/\">C program to add two numbers<\/a><br \/>\n<a href=\"https:\/\/prepbytes.com\/blog\/linked-list\/c-program-for-performing-bubble-sort-on-linked-list\/\">C program for performing bubble sort on linked list<\/a><br \/>\n<a href=\"https:\/\/prepbytes.com\/blog\/linked-list\/c-program-to-reverse-a-linked-list\/\">C program to reverse a linked list<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Introduction This blog post will guide you through implementing merge sort using linked lists in C. Sorting is a fundamental aspect of data structures. Before delving into the details of merge sort, let&#8217;s first grasp the basic concepts involved.. Problem Statement of merge sort using a linked list in C According to the problem statement, [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[125],"tags":[],"class_list":["post-5361","post","type-post","status-publish","format-standard","hentry","category-linked-list"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v25.8 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>C Program For Merge Sort For Linked Lists<\/title>\n<meta name=\"description\" content=\"In this blog, we have learned how to apply merge sort on a Singly Linked List. This is an important question when it comes to coding interviews.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"C Program For Merge Sort For Linked Lists\" \/>\n<meta property=\"og:description\" content=\"In this blog, we have learned how to apply merge sort on a Singly Linked List. This is an important question when it comes to coding interviews.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/\" \/>\n<meta property=\"og:site_name\" content=\"PrepBytes Blog\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prepbytes0211\/\" \/>\n<meta property=\"article:published_time\" content=\"2021-10-07T02:18:06+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2023-07-27T12:22:24+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645011665100-Article_188.png\" \/>\n<meta name=\"author\" content=\"PrepBytes\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"PrepBytes\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"5 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/\"},\"author\":{\"name\":\"PrepBytes\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/39fcf072e04987f16796546f2ca83c2e\"},\"headline\":\"C Program For Merge Sort For Linked Lists\",\"datePublished\":\"2021-10-07T02:18:06+00:00\",\"dateModified\":\"2023-07-27T12:22:24+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/\"},\"wordCount\":1157,\"commentCount\":0,\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645011665100-Article_188.png\",\"articleSection\":[\"Linked list articles\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/\",\"url\":\"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/\",\"name\":\"C Program For Merge Sort For Linked Lists\",\"isPartOf\":{\"@id\":\"http:\/\/43.205.93.38\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645011665100-Article_188.png\",\"datePublished\":\"2021-10-07T02:18:06+00:00\",\"dateModified\":\"2023-07-27T12:22:24+00:00\",\"description\":\"In this blog, we have learned how to apply merge sort on a Singly Linked List. This is an important question when it comes to coding interviews.\",\"breadcrumb\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/#primaryimage\",\"url\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645011665100-Article_188.png\",\"contentUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645011665100-Article_188.png\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"http:\/\/43.205.93.38\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Linked list articles\",\"item\":\"https:\/\/prepbytes.com\/blog\/category\/linked-list\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"C Program For Merge Sort For Linked Lists\"}]},{\"@type\":\"WebSite\",\"@id\":\"http:\/\/43.205.93.38\/#website\",\"url\":\"http:\/\/43.205.93.38\/\",\"name\":\"PrepBytes Blog\",\"description\":\"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING\",\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"http:\/\/43.205.93.38\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"http:\/\/43.205.93.38\/#organization\",\"name\":\"Prepbytes\",\"url\":\"http:\/\/43.205.93.38\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"contentUrl\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"width\":160,\"height\":160,\"caption\":\"Prepbytes\"},\"image\":{\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/www.facebook.com\/prepbytes0211\/\",\"https:\/\/www.instagram.com\/prepbytes\/\",\"https:\/\/www.linkedin.com\/company\/prepbytes\/\",\"https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA\"]},{\"@type\":\"Person\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/39fcf072e04987f16796546f2ca83c2e\",\"name\":\"PrepBytes\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/850669d326db1e1531f04db0c63145d941c2a26792aaeee226a9e6675b0ac698?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/850669d326db1e1531f04db0c63145d941c2a26792aaeee226a9e6675b0ac698?s=96&d=mm&r=g\",\"caption\":\"PrepBytes\"},\"url\":\"https:\/\/prepbytes.com\/blog\/author\/prepbytes\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"C Program For Merge Sort For Linked Lists","description":"In this blog, we have learned how to apply merge sort on a Singly Linked List. This is an important question when it comes to coding interviews.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/","og_locale":"en_US","og_type":"article","og_title":"C Program For Merge Sort For Linked Lists","og_description":"In this blog, we have learned how to apply merge sort on a Singly Linked List. This is an important question when it comes to coding interviews.","og_url":"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/","og_site_name":"PrepBytes Blog","article_publisher":"https:\/\/www.facebook.com\/prepbytes0211\/","article_published_time":"2021-10-07T02:18:06+00:00","article_modified_time":"2023-07-27T12:22:24+00:00","og_image":[{"url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645011665100-Article_188.png","type":"","width":"","height":""}],"author":"PrepBytes","twitter_card":"summary_large_image","twitter_misc":{"Written by":"PrepBytes","Est. reading time":"5 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/#article","isPartOf":{"@id":"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/"},"author":{"name":"PrepBytes","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/39fcf072e04987f16796546f2ca83c2e"},"headline":"C Program For Merge Sort For Linked Lists","datePublished":"2021-10-07T02:18:06+00:00","dateModified":"2023-07-27T12:22:24+00:00","mainEntityOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/"},"wordCount":1157,"commentCount":0,"publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645011665100-Article_188.png","articleSection":["Linked list articles"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/","url":"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/","name":"C Program For Merge Sort For Linked Lists","isPartOf":{"@id":"http:\/\/43.205.93.38\/#website"},"primaryImageOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/#primaryimage"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645011665100-Article_188.png","datePublished":"2021-10-07T02:18:06+00:00","dateModified":"2023-07-27T12:22:24+00:00","description":"In this blog, we have learned how to apply merge sort on a Singly Linked List. This is an important question when it comes to coding interviews.","breadcrumb":{"@id":"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/#primaryimage","url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645011665100-Article_188.png","contentUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645011665100-Article_188.png"},{"@type":"BreadcrumbList","@id":"https:\/\/prepbytes.com\/blog\/c-program-for-merge-sort-for-linked-lists\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"http:\/\/43.205.93.38\/"},{"@type":"ListItem","position":2,"name":"Linked list articles","item":"https:\/\/prepbytes.com\/blog\/category\/linked-list\/"},{"@type":"ListItem","position":3,"name":"C Program For Merge Sort For Linked Lists"}]},{"@type":"WebSite","@id":"http:\/\/43.205.93.38\/#website","url":"http:\/\/43.205.93.38\/","name":"PrepBytes Blog","description":"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING","publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"http:\/\/43.205.93.38\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"http:\/\/43.205.93.38\/#organization","name":"Prepbytes","url":"http:\/\/43.205.93.38\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/","url":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","contentUrl":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","width":160,"height":160,"caption":"Prepbytes"},"image":{"@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/prepbytes0211\/","https:\/\/www.instagram.com\/prepbytes\/","https:\/\/www.linkedin.com\/company\/prepbytes\/","https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA"]},{"@type":"Person","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/39fcf072e04987f16796546f2ca83c2e","name":"PrepBytes","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/850669d326db1e1531f04db0c63145d941c2a26792aaeee226a9e6675b0ac698?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/850669d326db1e1531f04db0c63145d941c2a26792aaeee226a9e6675b0ac698?s=96&d=mm&r=g","caption":"PrepBytes"},"url":"https:\/\/prepbytes.com\/blog\/author\/prepbytes\/"}]}},"_links":{"self":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/5361","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/comments?post=5361"}],"version-history":[{"count":10,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/5361\/revisions"}],"predecessor-version":[{"id":17378,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/5361\/revisions\/17378"}],"wp:attachment":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/media?parent=5361"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/categories?post=5361"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/tags?post=5361"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}