Posted on by Kalkicode
Code Sorting

# Merge sort on doubly linked list

Merge sort is a sorting algorithm that works by dividing the input array or linked list into smaller arrays or linked lists, sorting them recursively, and then merging them back together into a single, sorted output.

When applied to a doubly linked list, Merge sort works by dividing the list into two halves and recursively sorting each half. This is done by using a divide-and-conquer approach, where the list is repeatedly divided into smaller sub-lists until each sub-list contains only one element (which is already sorted).

After each sub-list is sorted, the two halves are merged back together by comparing the first element of each half and selecting the smaller one to be added to the sorted output list. This process is repeated until all elements have been merged back together into a single, sorted doubly linked list.

One advantage of using Merge sort on a doubly linked list is that it is relatively easy to implement because the links between the nodes can be easily adjusted during the merge process. Additionally, Merge sort has a time complexity of O(nlogn) in the worst case, which makes it efficient for large lists.

## Program Solution

``````/*
C Program
Merge sort for doubly linked list
*/
#include <stdio.h>
#include <stdlib.h>

{
int element;
};
struct DoublyLL
{
};
// Returns the new linked list
{
struct DoublyLL *dll = (struct DoublyLL *) malloc(sizeof(struct DoublyLL));
if (dll == NULL)
{
printf("Memory overflow\n");
}
else
{
dll->front = NULL;
dll->rear = NULL;
}
return dll;
}
void addNode(struct DoublyLL *dll, int element)
{
// Make a new node
if (node != NULL)
{
// Set node values
node->element = element;
node->next = NULL;
node->prev = NULL;
if (dll->front == NULL)
{
//  When inserting a first node of doubly linked list
dll->front = node;
dll->rear = node;
}
else
{
// Add node at end position
dll->rear->next = node;
node->prev = dll->rear;
dll->rear = node;
}
}
else
{
printf("\n Memory Overflow, when creating a new doubly linked list Node\n");
}
}
// Display element
void printData(struct DoublyLL *dll)
{
printf("\n Linked List of from front to rear \n");
// Display node of from front to rear
while (node != NULL)
{
printf(" %d →", node->element);
node = node->next;
}
printf(" NULL ");
printf("\n Linked List of from rear to front \n");
node = dll->rear;
// Display node of from rear to front
while (node != NULL)
{
printf(" %d →", node->element);
node = node->prev;
}
printf(" NULL \n");
}
//This are returning middle node of given linked list
{
{
}
else
{
//Auxiliary variables
while (high != NULL && high->next != NULL && high->next->next != NULL && high->next != tail && head->next->next != tail)
{
//visit to next node
low = low->next;
//visit to second next node
high = high->next->next;
}
//This is middle element
return low;
}
}
// Merge two sorted list and return its result
{
if (list1 == NULL)
{
//When list1 is empty
return list2;
}
else if (list2 == NULL)
{
return list1;
}
else
{
// Some auxiliary variables
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != NULL || list2 != NULL)
{
if (list1 != NULL && list2 != NULL)
{
//When both list contain nodes
if (list1->element < list2->element)
{
//When first list element are smallest
node = list1;
list1 = list1->next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2->next;
}
}
else if (list1 != NULL)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = NULL;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = NULL;
}
if (result == NULL)
{
//When get first node of resultant list
result = node;
node->next = NULL;
node->prev = NULL;
}
else
{
//Add node at end of resultant list
tail->next = node;
node->prev = tail;
}
tail = node;
}
return result;
}
}
// Perform merge sort
{
{
// When have zero or one node
}
// Find the relative middle node
// Get the right sublist
struct LinkNode *right = mergeSort(middle->next, tail);
// Separating sublist
if (middle->next != NULL)
{
middle->next->prev = NULL;
}
middle->next = NULL;
//Get the left sublist
// Sorted merge in two list
return mergeList(left, right);
}
// Handles the request to perform merge sort operation
void sortList(struct DoublyLL *dll)
{
dll->front = mergeSort(dll->front, dll->rear);
// First last node
while (node->next != NULL)
{
node = node->next;
}
// Set new rear node
dll->rear = node;
}
int main(int argc, char
const *argv[])
{
printf("\n Before Sort  ");
// 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
printData(dll);
sortList(dll);
printf("\n After Sort  ");
//-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
printData(dll);
return 0;
}``````

#### Output

`````` Before Sort
Linked List of from front to rear
5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
Linked List of from rear to front
0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL

After Sort
Linked List of from front to rear
-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
Linked List of from rear to front
9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL``````
``````/*
Java Program
Merge sort for doubly linked list
*/
{
public int element;
{
this.element = element;
this.next = null;
this.prev = null;
}
}
class DoublyLL
{
public DoublyLL()
{
this.front = null;
this.rear = null;
}
{
// Make a new node
if (this.front == null)
{
//  When inserting a first node of doubly linked list
this.front = node;
this.rear = node;
}
else
{
// Add node at end position
this.rear.next = node;
node.prev = this.rear;
this.rear = node;
}
}
// Display element
public void printData()
{
System.out.print("\n Linked List of from front to rear \n");
// Display node of from front to rear
while (node != null)
{
System.out.print(" " + node.element + " →");
node = node.next;
}
System.out.print(" NULL ");
System.out.print("\n Linked List of from rear to front \n");
node = this.rear;
// Display node of from rear to front
while (node != null)
{
System.out.print(" " + node.element + " →");
node = node.prev;
}
System.out.print(" NULL \n");
}
}
public class Sorting
{
//This are returning middle node of given linked list
{
{
}
else
{
//Auxiliary variables
while (high != null && high.next != null && high.next.next != null && high.next != tail && head.next.next != tail)
{
//visit to next node
low = low.next;
//visit to second next node
high = high.next.next;
}
//This is middle element
return low;
}
}
// Merge two sorted list and return its result
{
if (list1 == null)
{
//When list1 is empty
return list2;
}
else if (list2 == null)
{
return list1;
}
else
{
// Some auxiliary variables
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != null || list2 != null)
{
if (list1 != null && list2 != null)
{
//When both list contain nodes
if (list1.element < list2.element)
{
//When first list element are smallest
node = list1;
list1 = list1.next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2.next;
}
}
else if (list1 != null)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = null;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = null;
}
if (result == null)
{
//When get first node of resultant list
result = node;
node.next = null;
node.prev = null;
}
else
{
//Add node at end of resultant list
tail.next = node;
node.prev = tail;
}
tail = node;
}
return result;
}
}
// Perform merge sort
{
{
// When have zero or one node
}
// Find the relative middle node
// Get the right sublist
// Separating sublist
if (middle.next != null)
{
middle.next.prev = null;
}
middle.next = null;
//Get the left sublist
// Sorted merge in two list
return mergeList(left, right);
}
// Handles the request to perform merge sort operation
public void sortList(DoublyLL dll)
{
dll.front = mergeSort(dll.front, dll.rear);
// First last node
while (node.next != null)
{
node = node.next;
}
// Set new rear node
dll.rear = node;
}
public static void main(String[] args)
{
DoublyLL dll = new DoublyLL();
System.out.print("\n Before Sort \n");
// 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
dll.printData();
System.out.print("\n After Sort \n");
//-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
dll.printData();
}
}``````

#### Output

`````` Before Sort

Linked List of from front to rear
5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
Linked List of from rear to front
0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL

After Sort

Linked List of from front to rear
-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
Linked List of from rear to front
9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ Program
Merge sort for doubly linked list
*/
{
public: int element;
{
this->element = element;
this->next = NULL;
this->prev = NULL;
}
};
class DoublyLL
{
DoublyLL()
{
this->front = NULL;
this->rear = NULL;
}
{
// Make a new node
if (this->front == NULL)
{
//  When inserting a first node of doubly linked list
this->front = node;
this->rear = node;
}
else
{
// Add node at end position
this->rear->next = node;
node->prev = this->rear;
this->rear = node;
}
}
// Display element
void printData()
{
cout << "\n Linked List of from front to rear \n";
// Display node of from front to rear
while (node != NULL)
{
cout << " " << node->element << " →";
node = node->next;
}
cout << " NULL ";
cout << "\n Linked List of from rear to front \n";
node = this->rear;
// Display node of from rear to front
while (node != NULL)
{
cout << " " << node->element << " →";
node = node->prev;
}
cout << " NULL \n";
}
};
class Sorting
{
public:
//This are returning middle node of given linked list
{
{
}
else
{
//This is middle element
//Auxiliary variables
while (high != NULL && high->next != NULL && high->next->next != NULL && high->next != tail && head->next->next != tail)
{
//visit to next node
low = low->next;
//visit to second next node
high = high->next->next;
}
return low;
}
}
// Merge two sorted list and return its result
{
if (list1 == NULL)
{
//When list1 is empty
return list2;
}
else if (list2 == NULL)
{
return list1;
}
else
{
// Some auxiliary variables
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != NULL || list2 != NULL)
{
if (list1 != NULL && list2 != NULL)
{
//When both list contain nodes
if (list1->element < list2->element)
{
//When first list element are smallest
node = list1;
list1 = list1->next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2->next;
}
}
else if (list1 != NULL)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = NULL;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = NULL;
}
if (result == NULL)
{
//When get first node of resultant list
result = node;
node->next = NULL;
node->prev = NULL;
}
else
{
//Add node at end of resultant list
tail->next = node;
node->prev = tail;
}
tail = node;
}
return result;
}
}
// Perform merge sort
{
{
// When have zero or one node
}
// Find the relative middle node
// Get the right sublist
// Separating sublist
if (middle->next != NULL)
{
middle->next->prev = NULL;
}
middle->next = NULL;
//Get the left sublist
// Sorted merge in two list
return this->mergeList(left, right);
}
// Handles the request to perform merge sort operation
void sortList(DoublyLL *dll)
{
dll->front = this->mergeSort(dll->front, dll->rear);
// First last node
while (node->next != NULL)
{
node = node->next;
}
// Set new rear node
dll->rear = node;
}
};
int main()
{
DoublyLL dll = DoublyLL();
cout << "\n Before Sort \n";
// 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
dll.printData();
cout << "\n After Sort \n";
//-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
dll.printData();
return 0;
}``````

#### Output

`````` Before Sort

Linked List of from front to rear
5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
Linked List of from rear to front
0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL

After Sort

Linked List of from front to rear
-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
Linked List of from rear to front
9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL``````
``````// Include namespace system
using System;
/*
C# Program
Merge sort for doubly linked list
*/
{
public int element;
{
this.element = element;
this.next = null;
this.prev = null;
}
}
public class DoublyLL
{
public DoublyLL()
{
this.front = null;
this.rear = null;
}
{
// Make a new node
if (this.front == null)
{
//  When inserting a first node of doubly linked list
this.front = node;
this.rear = node;
}
else
{
// Add node at end position
this.rear.next = node;
node.prev = this.rear;
this.rear = node;
}
}
// Display element
public void printData()
{
Console.Write("\n Linked List of from front to rear \n");
// Display node of from front to rear
while (node != null)
{
Console.Write(" " + node.element + " →");
node = node.next;
}
Console.Write(" NULL ");
Console.Write("\n Linked List of from rear to front \n");
node = this.rear;
// Display node of from rear to front
while (node != null)
{
Console.Write(" " + node.element + " →");
node = node.prev;
}
Console.Write(" NULL \n");
}
}
public class Sorting
{
//This are returning middle node of given linked list
{
{
}
else
{
//This is middle element
//Auxiliary variables
while (high != null && high.next != null && high.next.next != null && high.next != tail && head.next.next != tail)
{
//visit to next node
low = low.next;
//visit to second next node
high = high.next.next;
}
return low;
}
}
// Merge two sorted list and return its result
{
if (list1 == null)
{
//When list1 is empty
return list2;
}
else if (list2 == null)
{
return list1;
}
else
{
// Some auxiliary variables
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != null || list2 != null)
{
if (list1 != null && list2 != null)
{
//When both list contain nodes
if (list1.element < list2.element)
{
//When first list element are smallest
node = list1;
list1 = list1.next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2.next;
}
}
else if (list1 != null)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = null;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = null;
}
if (result == null)
{
//When get first node of resultant list
result = node;
node.next = null;
node.prev = null;
}
else
{
//Add node at end of resultant list
tail.next = node;
node.prev = tail;
}
tail = node;
}
return result;
}
}
// Perform merge sort
{
{
// When have zero or one node
}
// Find the relative middle node
// Get the right sublist
// Separating sublist
if (middle.next != null)
{
middle.next.prev = null;
}
middle.next = null;
//Get the left sublist
// Sorted merge in two list
return mergeList(left, right);
}
// Handles the request to perform merge sort operation
public void sortList(DoublyLL dll)
{
dll.front = mergeSort(dll.front, dll.rear);
// First last node
while (node.next != null)
{
node = node.next;
}
// Set new rear node
dll.rear = node;
}
public static void Main(String[] args)
{
DoublyLL dll = new DoublyLL();
Console.Write("\n Before Sort \n");
// 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
dll.printData();
Console.Write("\n After Sort \n");
//-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
dll.printData();
}
}``````

#### Output

`````` Before Sort

Linked List of from front to rear
5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
Linked List of from rear to front
0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL

After Sort

Linked List of from front to rear
-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
Linked List of from rear to front
9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL``````
``````<?php
/*
Php Program
Merge sort for doubly linked list
*/
{
public \$element;
public \$next;
public \$prev;

function __construct(\$element)
{
\$this->element = \$element;
\$this->next = null;
\$this->prev = null;
}
}
class DoublyLL
{
public \$front;
public \$rear;

function __construct()
{
\$this->front = null;
\$this->rear = null;
}
{
// Make a new node
if (\$this->front == null)
{
//  When inserting a first node of doubly linked list
\$this->front = \$node;
\$this->rear = \$node;
}
else
{
// Add node at end position
\$this->rear->next = \$node;
\$node->prev = \$this->rear;
\$this->rear = \$node;
}
}
// Display element
public  function printData()
{
\$node = \$this->front;
echo "\n Linked List of from front to rear \n";
// Display node of from front to rear
while (\$node != null)
{
echo " ". \$node->element ." →";
\$node = \$node->next;
}
echo " NULL ";
echo "\n Linked List of from rear to front \n";
\$node = \$this->rear;
// Display node of from rear to front
while (\$node != null)
{
echo " ". \$node->element ." →";
\$node = \$node->prev;
}
echo " NULL \n";
}
}
class Sorting
{
//This are returning middle node of given linked list
{
{
}
else
{
//This is middle element
//Auxiliary variables
while (\$high != null && \$high->next != null && \$high->next->next != null && \$high->next != \$tail && \$head->next->next != \$tail)
{
//visit to next node
\$low = \$low->next;
//visit to second next node
\$high = \$high->next->next;
}
return \$low;
}
}
// Merge two sorted list and return its result
public  function mergeList(\$list1, \$list2)
{
if (\$list1 == null)
{
//When list1 is empty
return \$list2;
}
else if (\$list2 == null)
{
return \$list1;
}
else
{
// Some auxiliary variables
\$result = null;
\$tail = null;
\$node = null;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (\$list1 != null || \$list2 != null)
{
if (\$list1 != null && \$list2 != null)
{
//When both list contain nodes
if (\$list1->element < \$list2->element)
{
//When first list element are smallest
\$node = \$list1;
\$list1 = \$list1->next;
}
else
{
//When second list element are smallest
\$node = \$list2;
\$list2 = \$list2->next;
}
}
else if (\$list1 != null)
{
//When first list contain element
//Get sublist
\$node = \$list1;
//Set that list1 empty
\$list1 = null;
}
else
{
//When second list contain element
//get sublist
\$node = \$list2;
\$list2 = null;
}
if (\$result == null)
{
//When get first node of resultant list
\$result = \$node;
\$node->next = null;
\$node->prev = null;
}
else
{
//Add node at end of resultant list
\$tail->next = \$node;
\$node->prev = \$tail;
}
\$tail = \$node;
}
return \$result;
}
}
// Perform merge sort
{
{
// When have zero or one node
}
// Find the relative middle node
// Get the right sublist
\$right = \$this->mergeSort(\$middle->next, \$tail);
// Separating sublist
if (\$middle->next != null)
{
\$middle->next->prev = null;
}
\$middle->next = null;
//Get the left sublist
// Sorted merge in two list
return \$this->mergeList(\$left, \$right);
}
// Handles the request to perform merge sort operation
public  function sortList(\$dll)
{
\$dll->front = \$this->mergeSort(\$dll->front, \$dll->rear);
\$node = \$dll->front;
// First last node
while (\$node->next != null)
{
\$node = \$node->next;
}
// Set new rear node
\$dll->rear = \$node;
}
}

function main()
{
\$dll = new DoublyLL();
echo "\n Before Sort \n";
// 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
\$dll->printData();
echo "\n After Sort \n";
//-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
\$dll->printData();
}
main();``````

#### Output

`````` Before Sort

Linked List of from front to rear
5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
Linked List of from rear to front
0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL

After Sort

Linked List of from front to rear
-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
Linked List of from rear to front
9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL``````
``````/*
Node Js Program
Merge sort for doubly linked list
*/
{
constructor(element)
{
this.element = element;
this.next = null;
this.prev = null;
}
}
class DoublyLL
{
constructor()
{
this.front = null;
this.rear = null;
}
{
// Make a new node
if (this.front == null)
{
//  When inserting a first node of doubly linked list
this.front = node;
this.rear = node;
}
else
{
// Add node at end position
this.rear.next = node;
node.prev = this.rear;
this.rear = node;
}
}
// Display element
printData()
{
var node = this.front;
process.stdout.write("\n Linked List of from front to rear \n");
// Display node of from front to rear
while (node != null)
{
process.stdout.write(" " + node.element + " →");
node = node.next;
}
process.stdout.write(" NULL ");
process.stdout.write("\n Linked List of from rear to front \n");
node = this.rear;
// Display node of from rear to front
while (node != null)
{
process.stdout.write(" " + node.element + " →");
node = node.prev;
}
process.stdout.write(" NULL \n");
}
}
class Sorting
{
//This are returning middle node of given linked list
{
{
}
else
{
//This is middle element
//Auxiliary variables
while (high != null && high.next != null && high.next.next != null && high.next != tail && head.next.next != tail)
{
//visit to next node
low = low.next;
//visit to second next node
high = high.next.next;
}
return low;
}
}
// Merge two sorted list and return its result
mergeList(list1, list2)
{
if (list1 == null)
{
//When list1 is empty
return list2;
}
else if (list2 == null)
{
return list1;
}
else
{
// Some auxiliary variables
var result = null;
var tail = null;
var node = null;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != null || list2 != null)
{
if (list1 != null && list2 != null)
{
//When both list contain nodes
if (list1.element < list2.element)
{
//When first list element are smallest
node = list1;
list1 = list1.next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2.next;
}
}
else if (list1 != null)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = null;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = null;
}
if (result == null)
{
//When get first node of resultant list
result = node;
node.next = null;
node.prev = null;
}
else
{
//Add node at end of resultant list
tail.next = node;
node.prev = tail;
}
tail = node;
}
return result;
}
}
// Perform merge sort
{
{
// When have zero or one node
}
// Find the relative middle node
// Get the right sublist
var right = this.mergeSort(middle.next, tail);
// Separating sublist
if (middle.next != null)
{
middle.next.prev = null;
}
middle.next = null;
//Get the left sublist
// Sorted merge in two list
return this.mergeList(left, right);
}
// Handles the request to perform merge sort operation
sortList(dll)
{
dll.front = this.mergeSort(dll.front, dll.rear);
var node = dll.front;
// First last node
while (node.next != null)
{
node = node.next;
}
// Set new rear node
dll.rear = node;
}
}

function main()
{
var dll = new DoublyLL();
process.stdout.write("\n Before Sort \n");
// 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
dll.printData();
process.stdout.write("\n After Sort \n");
//-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
dll.printData();
}
main();``````

#### Output

`````` Before Sort

Linked List of from front to rear
5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
Linked List of from rear to front
0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL

After Sort

Linked List of from front to rear
-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
Linked List of from rear to front
9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL``````
``````#  Python 3 Program
#  Merge sort for doubly linked list

def __init__(self, element) :
self.element = element
self.next = None
self.prev = None

class DoublyLL :

def __init__(self) :
self.front = None
self.rear = None

#  Make a new node
if (self.front == None) :
#   When inserting a first node of doubly linked list
self.front = node
self.rear = node
else :
#  Add node at end position
self.rear.next = node
node.prev = self.rear
self.rear = node

#  Display element
def printData(self) :
node = self.front
print("\n Linked List of from front to rear ")
#  Display node of from front to rear
while (node != None) :
print("", node.element ,"→", end = "")
node = node.next

print(" NULL ", end = "")
print("\n Linked List of from rear to front ")
node = self.rear
#  Display node of from rear to front
while (node != None) :
print("", node.element ,"→", end = "")
node = node.prev

print(" NULL ")

class Sorting :
# This are returning middle node of given linked list
else :
# Auxiliary variables
while (high != None and high.next != None and high.next.next != None and high.next != tail and head.next.next != tail) :
# visit to next node
low = low.next
# visit to second next node
high = high.next.next

# This is middle element
return low

#  Merge two sorted list and return its result
def mergeList(self, list1, list2) :
if (list1 == None) :
# When list1 is empty
return list2

elif(list2 == None) :
return list1
else :
#  Some auxiliary variables
result = None
tail = None
node = None
#  Combine list elements in sorted order
#  This process takes(m+n) time
#  Here m is size of list1
#  And n is size of list2
while (list1 != None or list2 != None) :
if (list1 != None and list2 != None) :
# When both list contain nodes
if (list1.element < list2.element) :
# When first list element are smallest
node = list1
list1 = list1.next
else :
# When second list element are smallest
node = list2
list2 = list2.next

elif(list1 != None) :
# When first list contain element
# Get sublist
node = list1
# Set that list1 empty
list1 = None
else :
# When second list contain element
# get sublist
node = list2
list2 = None

if (result == None) :
# When get first node of resultant list
result = node
node.next = None
node.prev = None
else :
# Add node at end of resultant list
tail.next = node
node.prev = tail

tail = node

return result

#  Perform merge sort
#  When have zero or one node

#  Find the relative middle node
#  Get the right sublist
right = self.mergeSort(middle.next, tail)
#  Separating sublist
if (middle.next != None) :
middle.next.prev = None

middle.next = None
# Get the left sublist
#  Sorted merge in two list
return self.mergeList(left, right)

#  Handles the request to perform merge sort operation
def sortList(self, dll) :
dll.front = self.mergeSort(dll.front, dll.rear)
node = dll.front
#  First last node
while (node.next != None) :
node = node.next

#  Set new rear node
dll.rear = node

def main() :
dll = DoublyLL()
print("\n Before Sort ")
#  5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
dll.printData()
print("\n After Sort ")
# -2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
dll.printData()

if __name__ == "__main__": main()``````

#### Output

`````` Before Sort

Linked List of from front to rear
5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
Linked List of from rear to front
0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL

After Sort

Linked List of from front to rear
-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
Linked List of from rear to front
9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL``````
``````#  Ruby Program
#  Merge sort for doubly linked list

attr_accessor :element, :next, :prev

def initialize(element)
self.element = element
self.next = nil
self.prev = nil
end

end

class DoublyLL
# Define the accessor and reader of class DoublyLL
attr_accessor :front, :rear

def initialize()
self.front = nil
self.rear = nil
end

#  Make a new node
if (self.front == nil)
#   When inserting a first node of doubly linked list
self.front = node
self.rear = node
else
#  Add node at end position
self.rear.next = node
node.prev = self.rear
self.rear = node
end

end

#  Display element
def printData()
node = self.front
print("\n Linked List of from front to rear \n")
#  Display node of from front to rear
while (node != nil)
print(" ", node.element ," →")
node = node.next
end

print(" NULL ")
print("\n Linked List of from rear to front \n")
node = self.rear
#  Display node of from rear to front
while (node != nil)
print(" ", node.element ," →")
node = node.prev
end

print(" NULL \n")
end

end

class Sorting
# This are returning middle node of given linked list
else
# Auxiliary variables
while (high != nil && high.next != nil && high.next.next != nil && high.next != tail && head.next.next != tail)
# visit to next node
low = low.next
# visit to second next node
high = high.next.next
end

# This is middle element
return low
end

end

#  Merge two sorted list and return its result
def mergeList(list1, list2)
if (list1 == nil)
# When list1 is empty
return list2
elsif(list2 == nil)
return list1
else
#  Some auxiliary variables
result = nil
tail = nil
node = nil
#  Combine list elements in sorted order
#  This process takes(m+n) time
#  Here m is size of list1
#  And n is size of list2
while (list1 != nil || list2 != nil)
if (list1 != nil && list2 != nil)
# When both list contain nodes
if (list1.element < list2.element)
# When first list element are smallest
node = list1
list1 = list1.next
else
# When second list element are smallest
node = list2
list2 = list2.next
end

elsif(list1 != nil)
# When first list contain element
# Get sublist
node = list1
# Set that list1 empty
list1 = nil
else
# When second list contain element
# get sublist
node = list2
list2 = nil
end

if (result == nil)
# When get first node of resultant list
result = node
node.next = nil
node.prev = nil
else
# Add node at end of resultant list
tail.next = node
node.prev = tail
end

tail = node
end

return result
end

end

#  Perform merge sort
#  When have zero or one node
end

#  Find the relative middle node
#  Get the right sublist
right = self.mergeSort(middle.next, tail)
#  Separating sublist
if (middle.next != nil)
middle.next.prev = nil
end

middle.next = nil
# Get the left sublist
#  Sorted merge in two list
return self.mergeList(left, right)
end

#  Handles the request to perform merge sort operation
def sortList(dll)
dll.front = self.mergeSort(dll.front, dll.rear)
node = dll.front
#  First last node
while (node.next != nil)
node = node.next
end

#  Set new rear node
dll.rear = node
end

end

def main()
dll = DoublyLL.new()
print("\n Before Sort \n")
#  5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
dll.printData()
print("\n After Sort \n")
# -2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
dll.printData()
end

main()``````

#### Output

`````` Before Sort

Linked List of from front to rear
5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
Linked List of from rear to front
0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL

After Sort

Linked List of from front to rear
-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
Linked List of from rear to front
9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL
``````
``````/*
Scala Program
Merge sort for doubly linked list
*/
{
def this(element: Int)
{
this(element, null, null);
}
}
{
def this()
{
this(null, null);
}
def addNode(element: Int): Unit = {
// Make a new node
if (this.front == null)
{
//  When inserting a first node of doubly linked list
this.front = node;
this.rear = node;
}
else
{
// Add node at end position
this.rear.next = node;
node.prev = this.rear;
this.rear = node;
}
}
// Display element
def printData(): Unit = {
print("\n Linked List of from front to rear \n");
// Display node of from front to rear
while (node != null)
{
print(" " + node.element + " →");
node = node.next;
}
print(" NULL ");
print("\n Linked List of from rear to front \n");
node = this.rear;
// Display node of from rear to front
while (node != null)
{
print(" " + node.element + " →");
node = node.prev;
}
print(" NULL \n");
}
}
class Sorting
{
//This are returning middle node of given linked list
{
}
else
{
//This is middle element
//Auxiliary variables
while (high != null && high.next != null && high.next.next != null && high.next != tail && head.next.next != tail)
{
//visit to next node
low = low.next;
//visit to second next node
high = high.next.next;
}
return low;
}
}
// Merge two sorted list and return its result

if (list1 == null)
{
//When list1 is empty
return list2;
}
else if (list2 == null)
{
return list1;
}
else
{
// Some auxiliary variables
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != null || list2 != null)
{
if (list1 != null && list2 != null)
{
//When both list contain nodes
if (list1.element < list2.element)
{
//When first list element are smallest
node = list1;
list1 = list1.next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2.next;
}
}
else if (list1 != null)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = null;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = null;
}
if (result == null)
{
//When get first node of resultant list
result = node;
node.next = null;
node.prev = null;
}
else
{
//Add node at end of resultant list
tail.next = node;
node.prev = tail;
}
tail = node;
}
return result;
}
}
// Perform merge sort
{
// When have zero or one node
}
// Find the relative middle node
// Get the right sublist
var right: LinkNode = this.mergeSort(middle.next, tail);
// Separating sublist
if (middle.next != null)
{
middle.next.prev = null;
}
middle.next = null;
//Get the left sublist
// Sorted merge in two list
return this.mergeList(left, right);
}
// Handles the request to perform merge sort operation
def sortList(dll: DoublyLL): Unit = {
dll.front = this.mergeSort(dll.front, dll.rear);
// First last node
while (node.next != null)
{
node = node.next;
}
// Set new rear node
dll.rear = node;
}
}
object Main
{
def main(args: Array[String]): Unit = {
var dll: DoublyLL = new DoublyLL();
var task: Sorting = new Sorting();
print("\n Before Sort \n");
// 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
dll.printData();
print("\n After Sort \n");
//-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
dll.printData();
}
}``````

#### Output

`````` Before Sort

Linked List of from front to rear
5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
Linked List of from rear to front
0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL

After Sort

Linked List of from front to rear
-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
Linked List of from rear to front
9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL``````
``````/*
Swift 4 Program
Merge sort for doubly linked list
*/
{
var element: Int;
init(_ element: Int)
{
self.element = element;
self.next = nil;
self.prev = nil;
}
}
class DoublyLL
{
init()
{
self.front = nil;
self.rear = nil;
}
{
// Make a new node
if (self.front == nil)
{
//  When inserting a first node of doubly linked list
self.front = node;
self.rear = node;
}
else
{
// Add node at end position
self.rear!.next = node;
node!.prev = self.rear;
self.rear = node;
}
}
// Display element
func printData()
{
print("\n Linked List of from front to rear ");
// Display node of from front to rear
while (node  != nil)
{
print("", node!.element ,"→", terminator: "");
node = node!.next;
}
print(" NULL ", terminator: "");
print("\n Linked List of from rear to front ");
node = self.rear;
// Display node of from rear to front
while (node  != nil)
{
print("", node!.element ,"→", terminator: "");
node = node!.prev;
}
print(" NULL ");
}
}
class Sorting
{
//This are returning middle node of given linked list
{
{
}
else
{
//This is middle element
//Auxiliary variables
while (high  != nil && high!.next  != nil
&& high!.next!.next  != nil
&& !(high!.next  === tail) && !(head!.next!.next  === tail))
{
//visit to next node
low = low!.next;
//visit to second next node
high = high!.next!.next;
}
return low;
}
}
// Merge two sorted list and return its result
{

if (list1 == nil)
{
//When list1 is empty
return list2;
}
else if (list2 == nil)
{
return list1;
}
else
{
// Some auxiliary variables
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1  != nil || list2  != nil)
{
if (list1  != nil && list2  != nil)
{
//When both list contain nodes
if (list1!.element < list2!.element)
{
//When first list element are smallest
node = list1;
list1 = list1!.next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2!.next;
}
}
else if (list1  != nil)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = nil;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = nil;
}
if (result == nil)
{
//When get first node of resultant list
result = node;
node!.next = nil;
node!.prev = nil;
}
else
{
//Add node at end of resultant list
tail!.next = node;
node!.prev = tail;
}
tail = node;
}
return result;
}
}
// Perform merge sort
{
{
// When have zero or one node
}
// Find the relative middle node
// Get the right sublist
let right: LinkNode? = self.mergeSort(middle!.next, tail);
// Separating sublist
if (middle!.next  != nil)
{
middle!.next!.prev = nil;
}
middle!.next = nil;
//Get the left sublist
// Sorted merge in two list
return self.mergeList(left, right);
}
// Handles the request to perform merge sort operation
func sortList(_ dll: DoublyLL? )
{
dll!.front = self.mergeSort(dll!.front, dll!.rear);
// First last node
while (node!.next  != nil)
{
node = node!.next;
}
// Set new rear node
dll!.rear = node;
}
}
func main()
{
let dll: DoublyLL = DoublyLL();
print("\n Before Sort ");
// 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
dll.printData();
print("\n After Sort ");
//-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
dll.printData();
}
main();``````

#### Output

`````` Before Sort

Linked List of from front to rear
5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
Linked List of from rear to front
0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL

After Sort

Linked List of from front to rear
5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
Linked List of from rear to front
0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL``````
``````/*
Kotlin Program
Merge sort for doubly linked list
*/
{
var element: Int;
constructor(element: Int)
{
this.element = element;
this.next = null;
this.prev = null;
}
}
class DoublyLL
{
constructor()
{
this.front = null;
this.rear = null;
}
{
// Make a new node
if (this.front == null)
{
//  When inserting a first node of doubly linked list
this.front = node;
this.rear = node;
}
else
{
// Add node at end position
this.rear?.next = node;
node?.prev = this.rear;
this.rear = node;
}
}
// Display element
fun printData(): Unit
{
var node: LinkNode ? = this.front;
print("\n Linked List of from front to rear \n");
// Display node of from front to rear
while (node != null)
{
print(" " + node.element + " →");
node = node.next;
}
print(" NULL ");
print("\n Linked List of from rear to front \n");
node = this.rear;
// Display node of from rear to front
while (node != null)
{
print(" " + node.element + " →");
node = node.prev;
}
print(" NULL \n");
}
}
class Sorting
{
//This are returning middle node of given linked list
{
{
}
else
{
//This is middle element
//Auxiliary variables
while (high != null
&& high.next != null
&& high.next?.next != null
&& high.next != tail
{
//visit to next node
low = low?.next;
//visit to second next node
high = high.next?.next;
}
return low;
}
}
// Merge two sorted list and return its result
{

var list1: LinkNode ? = l1;
var list2: LinkNode ? = l2;
if (list1 == null)
{
//When list1 is empty
return list2;
}
else if (list2 == null)
{
return list1;
}
else
{
// Some auxiliary variables
var result: LinkNode ? = null;
var tail: LinkNode ? = null;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != null || list2 != null)
{
if (list1 != null && list2 != null)
{
//When both list contain nodes
if (list1.element < list2.element)
{
//When first list element are smallest
node = list1;
list1 = list1.next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2.next;
}
}
else if (list1 != null)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = null;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = null;
}
if (result == null)
{
//When get first node of resultant list
result = node;
node?.next = null;
node?.prev = null;
}
else
{
//Add node at end of resultant list
tail?.next = node;
node?.prev = tail;
}
tail = node;
}
return result;
}
}
// Perform merge sort
{
{
// When have zero or one node
}
// Find the relative middle node
// Get the right sublist
var right: LinkNode ? = this.mergeSort(middle?.next, tail);
// Separating sublist
if (middle?.next != null)
{
middle.next?.prev = null;
}
middle?.next = null;
//Get the left sublist

// Sorted merge in two list
return this.mergeList(left, right);
}
// Handles the request to perform merge sort operation
fun sortList(dll: DoublyLL ): Unit
{
dll.front = this.mergeSort(dll.front, dll.rear);
var node: LinkNode ? = dll.front;
// First last node
while (node?.next != null)
{
node = node.next;
}
// Set new rear node
dll.rear = node;
}
}
fun main(args: Array < String > ): Unit
{
var dll: DoublyLL = DoublyLL();
print("\n Before Sort \n");
// 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
dll.printData();
print("\n After Sort \n");
//-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
dll.printData();
}``````

#### Output

`````` Before Sort

Linked List of from front to rear
5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
Linked List of from rear to front
0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL

After Sort

Linked List of from front to rear
-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
Linked List of from rear to front
9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL``````

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post