Solution: Sorting Algorithms

import java.util.Comparator;

public class MergeSortDLL < T > {
  private Node < T > head;
  private Comparator < T > comparator;

  class Node < T > {
    T data;
    Node < T > prev;
    Node < T > next;

    public Node(T data) {
      this.data = data;
      this.prev = null;
      this.next = null;
    }
  }
  // Constructor
  public MergeSortDLL(Comparator < T > comparator) {
    this.head = null;
    this.comparator = comparator;
  }
  // Adds a new node with the given data to the doubly linked list
  public void add(T data) {
    Node < T > newNode = new Node < > (data);
    if (head == null) {
      head = newNode;
    } else {
      Node < T > current = head;
      while (current.next != null) {
        current = current.next;
      }
      current.next = newNode;
      newNode.prev = current;
    }
  }
  // Sorts the doubly linked list using merge sort
  public void mergeSort() {
    head = mergeSort(head);
  }
  // Recursively performs merge sort on the given doubly linked list and returns the sorted list
  private Node < T > mergeSort(Node < T > head) {
    if (head == null || head.next == null) {
      return head;
    }

    Node < T > middle = getMiddle(head);
    Node < T > nextOfMiddle = middle.next;
    middle.next = null;

    Node < T > left = mergeSort(head);
    Node < T > right = mergeSort(nextOfMiddle);

    return merge(left, right);
  }
  // Merges two sorted doubly linked lists and returns the merged list
  private Node < T > merge(Node < T > left, Node < T > right) {
    Node < T > result = null;

    if (left == null) {
      return right;
    }
    if (right == null) {
      return left;
    }

    if (comparator.compare(left.data, right.data) <= 0) {
      result = left;
      result.next = merge(left.next, right);
      result.next.prev = result;
    } else {
      result = right;
      result.next = merge(left, right.next);
      result.next.prev = result;
    }

    return result;
  }
  // Returns the middle node of the doubly linked list
  private Node < T > getMiddle(Node < T > head) {
    if (head == null) {
      return null;
    }

    Node < T > slow = head;
    Node < T > fast = head.next;

    while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
    }

    return slow;
  }
  // Prints the elements of the doubly linked list
  public void printList() {
    Node < T > current = head;
    while (current != null) {
      System.out.print(current.data + " ");
      current = current.next;
    }
    System.out.println();
  }

  public static void main(String[] args) {
    MergeSortDLL < Integer > mergeSortDLL = new MergeSortDLL < Integer > (Comparator. < Integer > naturalOrder());
    mergeSortDLL.add(5);
    mergeSortDLL.add(2);
    mergeSortDLL.add(9);
    mergeSortDLL.add(1);
    mergeSortDLL.add(3);
    mergeSortDLL.add(6);

    System.out.print("Original List: ");
    mergeSortDLL.printList();

    mergeSortDLL.mergeSort();

    System.out.print("Sorted List: ");
    mergeSortDLL.printList();
  }
}