Merge Sort for Doubly Linked List

This is a recursive procedure based on divide and conquer techniques to solve the problem. This means dividing the main problem into smaller ones and merging them later to get a solution to the bigger one. Merge sort splits the list of items into smaller lists until a single item remains in the list, then combines them in the correct order to get the ordered list of items. It is also a classification algorithm based on O (nlogn) complexity. This section describes the type of data structure combination, along with its algorithms and examples.

Merge sort algorithm:

  1. Returns the list if the header is null or if the list has only one element.
  2. Divide the original list into two parts to create two lists.
  3. Order the first and second parts of the list.
  4. Merge both ordered lists

The following is an implementation of the double linked list join sorting.

For example:

merge sort

merge sort

merge sort

merge sort

Here Code:

#include <iostream>
#include <new>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
struct node {
   int data;
   struct node *next;
   struct node *prev;
};
node *createList(int *arr, int n){
   node *head, *p, *q;
   p = head = new node;
   head->data = arr[0];
   head->prev = NULL;
   head->next = NULL;
   for (int i = 1; i < n; ++i) {
      q = new node;
      q->data = arr[i];
      q->prev = p;
      q->next = NULL;
      p->next = q;
      p = q;
   }
   return head;
}
void displayList(node *head){
   while (head != NULL) {
      cout << head->data << " ";
      head = head->next;
   }
   cout << endl;
}
node *mergeSortedLists(node *head1, node *head2){
   node *result = NULL;
   if (head1 == NULL) {
      return head2;
   }
   if (head2 == NULL) {
      return head1;
   }
   if (head1->data < head2->data) {
      head1->next = mergeSortedLists(head1->next, head2);
      head1->next->prev = head1;
      head1->prev = NULL;
      return head1;
   } else {
      head2->next = mergeSortedLists(head1, head2->next);
      head2->next->prev = head2;
      head2->prev = NULL;
      return head2;
   }
}
void splitList(node *src, node **fRef, node **bRef){
   node *fast;
   node *slow;
   slow = src;
   fast = src->next;
   while (fast != NULL) {
      fast = fast->next;
      if (fast != NULL) {
         slow = slow->next;
         fast = fast->next;
      }
   }
   *fRef = src;
   *bRef = slow->next;
   slow->next = NULL;
}
void mergeSort(node **head){
   node *p = *head;
   node *a = NULL;
   node *b = NULL;
   if (p == NULL || p->next == NULL) {
      return;
   }
   splitList(p, &a, &b);
   mergeSort(&a);
   mergeSort(&b);
   *head = mergeSortedLists(a, b);
}
int main(){
   int arr[] = {10, 20, 8, 17, 5, 13, 4};
   node *head;
   head = createList(arr, SIZE(arr));
   cout << "Unsorted list: " << endl;
   displayList(head);
   mergeSort(&head);
   cout << "Final sorted list: " << endl;
   displayList(head);
   return 0;
}

Complexity Analysis:

  • Time Complexity: The time complexity of the above implementation is the same as the time complexity of the array merge classification. Θ (nLogn) It takes time.

Conclusion:

Merge sort is a divide and conquer algorithm that uses the merge process to combine two subarrays into one by sorting the items out of order. The elements of these subarrays work on the assumption that they are already ordered. This is a stable algorithm that is often used for investment counting and linked list problems, or for external ranking.

Recommended Articles:

  1. Insertion in Doubly Linked List
  2. Deletion in Doubly Linked List
  3. How to reverse a doubly linked list?
  4. QuickSort on Doubly Linked List
  5. How to reverse a string using stack?

References:

Help Me Please: If you found any error in the content or example please let us know by comment also write your suggestion or if any doubt in the concept please feel free to write us in the comment section.

Practice your Code online here

(Visited 21 times, 1 visits today)

0 0 votes
Article Rating
Subscribe
Notify of
9 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
trackback

[…] Merge Sort for Doubly Linked List […]

trackback

[…] Merge Sort for Doubly Linked List […]

trackback

[…] Merge Sort for Doubly Linked List […]

trackback

[…] Merge Sort for Doubly Linked List […]

trackback

[…] Merge Sort for Doubly Linked List […]

trackback

[…] Merge Sort for Doubly Linked List […]

trackback

[…] Merge Sort for Doubly Linked List […]

trackback

[…] Merge Sort for Doubly Linked List […]

trackback

[…] Merge Sort for Doubly Linked List […]

You cannot copy content of this page
Scroll Up
9
0
Would love your thoughts, please comment.x
()
x

  • Name

  • Minimum length of 8 characters.