using System;

​

public class Program

{

    public static void Main()

    {

        int[] arr = new int[]{20,10,60,80,70};

        Node head = CreateSLL(arr);

        //starting from head to find the end.

        Node end = head;

        while(end.next !=null)

        {

            end = end.next;

        }

        //head of the sorted list.

        head = Sort(head, end);

        PrintSLL(head);

    }

    public static Node Sort(Node start, Node end)

    {

        Node head = start;

        if(start != end)

        {

​

            Console.WriteLine($"{start.data}, {end.data}");

            Node p = Partition(start,end);

​

            if(p.next != null)

            {

                Sort(p.next.next,end);

            }

​

            Node prev = start;

​

            while(prev.next != p)

            {

                prev = prev.next;

            }

​

            Sort(start, prev);

        }

        return head;

    }

    public static Node Partition(Node start, Node end)

    {

        int pivot = end.data;

        Node prev = start;

        int temp;

        while(start != end)

        {

            Console.WriteLine($"start data: {start.data}");

            if(start.data < pivot)

            {

                temp = prev.data;

                prev.data = start.data;

                start.data = temp;

                prev= prev.next;

                Console.WriteLine($"prev data: {prev.data}");

            }

            start = start.next;

        }

        //swap the pivot to its position.

        temp = prev.data;

        prev.data = end.data;

        end.data = temp;

        return prev.next;

    }

    public static Node CreateSLL(int[] arr)

    {

        Node head = null;

        head = new Node(arr[0]);

        Node n1 = head;     

        for(int i = 1; i < arr.Length; i++)

        {

            n1.next = new Node(arr[i]);

            n1 = n1.next;

        }

        return head;

    }

    public static void PrintSLL(Node head)

    {

        string data = "";

        while(head !=  null)

        {

            data += head.data + "->";

            head = head.next;

        }

        Console.WriteLine($"LL: {data}");

    }

}

​

public class Node

{

    public int data;

    public Node next;

    public Node(int data)

    {

        this.data = data;

        this.next = null;

    }

}