Sort array using stack

The problem is to sort an array using a stack data structure. The goal is to implement a sorting algorithm that utilizes a stack to sort the array in non-decreasing order.

Problem Statement

Given an array of integers, we need to sort the array using a stack data structure.

Explanation with Suitable Example

Let's consider the following unsorted array:

int arr[] = {6, 1, 0, 5, -2, 8, 2, 3, 6, -3, 62, 21};

The goal is to sort this array in non-decreasing order.

Idea to Solve the Problem

The main idea behind sorting an array using a stack is to mimic the process of insertion sort. We can use a stack to store the elements in a partially sorted order. While iterating through the array, we compare the current array element with the top element of the stack. If the array element is greater than or equal to the top of the stack, we push it onto the stack. Otherwise, we pop elements from the stack until we find the right position for the current element and insert it accordingly.

Pseudocode

The following pseudocode outlines the steps to sort an array using a stack:

function sort_array(arr[], size)
    if size <= 0, return
    create an empty stack
    for i from 0 to size-1
        if stack is empty or arr[i] >= top of stack
            push arr[i] onto the stack
        else
            initialize temp to arr[i]
            initialize j to i
            while stack is not empty and top of stack > temp
                arr[j] = pop top of stack
                decrement j
            arr[j] = temp
            push arr[j] onto the stack
    for i from size-1 to 0
        arr[i] = pop top of stack

Algorithm Explanation

1. Check if the size of the array is non-positive (size <= 0), if so, return as there is nothing to sort.
2. Create an empty stack to store the elements in a partially sorted order.
3. Use a loop to iterate through the array from index 0 to size-1.
   • If the stack is empty or the current array element is greater than or equal to the top of the stack, push the current array element onto the stack.
   • Otherwise, initialize a temporary variable (temp) with the current array element and a variable j with i.
   • While the stack is not empty and the top of the stack is greater than the temp value, pop the top of the stack and assign it to arr[j]. Decrement j.
   • Finally, assign the temp value to arr[j] and push arr[j] onto the stack.
4. Use another loop to iterate through the array from index size-1 to 0.
   • Pop the top of the stack and assign it to arr[i].

Code Solution

• C
• Java
• C++
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4

//C Program
//Sort array using stack
#include <stdio.h>

#include <stdlib.h> //for malloc function

//create structure of stack Node
struct Node
{
	int data;
	struct Node *next;
};
//insert Stack element
void push(int value, struct Node **top)
{
	//Create dynamic node
	struct Node *node = (struct Node *) malloc(sizeof(struct Node));
	if (node == NULL)
	{
		printf("Memory overflow\n");
	}
	else
	{
		node->data = value;
		node->next = *top;*top = node;
	}
}
//pop Stack element
int pop(struct Node **top)
{
	int value = 0;
	if ( *top == NULL)
	{
		printf("Empty Stack\n");
	}
	else
	{
		struct Node *temp = *top;
		value = temp->data;*top = temp->next;
		free(temp);
		temp = NULL;
	}
	return value;
}
//Get value of top element
int peek(struct Node *top)
{
	if (top != NULL)
	{
		return top->data;
	}
	else
	{
		return -1;
	}
}
//Sort array element by using stack
void sort_array(int arr[], int size)
{
	if (size <= 0)
	{
		return;
	}
	struct Node *top = NULL;
	int temp = 0, j = 0;
	for (int i = 0; i < size; ++i)
	{
		if (top == NULL || peek(top) <= arr[i])
		{
			//Add array element into stack when stack is empty, 
			//or array element is greater than equal to top of stack
			push(arr[i], & top);
		}
		else
		{
			j = i;
			temp = arr[j];
			//When array element is less than stack top element
			//Then insert new element in its proper position
			while (top != NULL && peek(top) > temp)
			{
				//use array space and assign the stack element 
				//until stack top is not null or its value 
				//is less than current array element
				arr[j] = pop( & top);
				j--;
			}
			//assign current element
			arr[j] = temp;
			//After that  array elements between given index is add to stack
			for (j; j <= i; j++)
			{
				push(arr[j], & top);
			}
		}
	}
	//Assign the sorted value in actual array
	for (int i = size - 1; i >= 0; --i)
	{
		arr[i] = pop( & top);
	}
}
//Display array elements
void display(int arr[], int size)
{
	for (int i = 0; i < size; ++i)
	{
		printf("%d  ", arr[i]);
	}
	printf("\n");
}
int main()
{
	//Define the element of unsorted array
	int arr[] = {6,1,0,5,-2,8,2,3,6,-3,62,21};
	//Get the size of array
	int size = sizeof(arr) / sizeof(arr[0]);
	display(arr, size);
	sort_array(arr, size);
	display(arr, size);
	return 0;
}

6  1  0  5  -2  8  2  3  6  -3  62  21
-3  -2  0  1  2  3  5  6  6  8  21  62

/*
  Java Program
  Sort array using stack
*/
//Stack Node
class Node
{
  public int data;
  public Node next;
  public Node(int data)
  {
    this.data = data;
    this.next = null;
  }
}
class MyStack
{
  public Node top;
  public MyStack()
  {
    top = null;
  }
  public void display()
  {
    if (top != null)
    {
      Node temp = top;
      while (temp != null)
      {
        System.out.print(" " + temp.data);
        temp = temp.next;
      }
    }
    System.out.print("\n");
  }
  //Add a new element in stack
  public void push(int data)
  {
    //Make a new stack node
    Node new_node = new Node(data);
    if (new_node != null)
    {
      new_node.next = top;
      top = new_node;
    }
    else
    {
      System.out.print("Memory overflow\n");
    }
  }
  //Add a top element in stack
  //When stack is empty it returns -1
  public int pop()
  {
    int temp = -1;
    if (top != null)
    {
      temp = top.data;
      top = top.next;
    }
    return temp;
  }
  public boolean is_empty()
  {
    if (this.top != null)
    {
      return false;
    }
    else
    {
      return true;
    }
  }
  //Used to get top element of stack
  public int peek()
  {
    if (top != null)
    {
      return top.data;
    }
    else
    {
      return -1;
    }
  }
  //Sort array element by using stack
  public void sort_array(int[] arr, int size)
  {
    if (size <= 0)
    {
      return;
    }
    int temp = 0, j = 0, k = 0;
    for (int i = 0; i < size; ++i)
    {
      if (this.is_empty() || this.peek() <= arr[i])
      {
        //Add array element into stack when stack is empty, 
        //or array element is greater than equal to top of stack
        this.push(arr[i]);
      }
      else
      {
        j = i;
        temp = arr[j];
        //When array element is less than stack top element
        //Then insert new element in its proper position
        while (!this.is_empty() && this.peek() > temp)
        {
          //use array space and assign the stack element 
          //until stack top is not null or its value 
          //is less than current array element
          arr[j] = this.pop();
          j--;
        }
        //assign current element
        arr[j] = temp;
        //After that  array elements between given index is add to stack
        for (k = j; k <= i; k++)
        {
          this.push(arr[k]);
        }
      }
    }
    //Assign the sorted value in actual array
    for (int i = size - 1; i >= 0; --i)
    {
      arr[i] = this.pop();
    }
  }
  //Display array elements
  public void display(int[] arr, int size)
  {
    for (int i = 0; i < size; ++i)
    {
      System.out.print(" " + arr[i]);
    }
    System.out.print("\n");
  }
  public static void main(String[] args)
  {
    MyStack obj = new MyStack();
    //Define the element of unsorted array
    int[] arr = {6,1,0,5,-2,8,2,3,6,-3,62,21};
    //Get the size of array
    int size = arr.length;
    obj.display(arr, size);
    obj.sort_array(arr, size);
    obj.display(arr, size);
  }
}

 6 1 0 5 -2 8 2 3 6 -3 62 21
 -3 -2 0 1 2 3 5 6 6 8 21 62

/*
  C++ Program
  Sort array using stack
*/
//Stack Node
#include<iostream>

using namespace std;
class Node
{
	public: 
    int data;
	Node * next;
	Node(int data)
	{
		this->data = data;
		this->next = NULL;
	}
};
class MyStack
{
	public: 
    Node * top;
	MyStack()
	{
		this->top = NULL;
	}
	void display()
	{
		if (this->top != NULL)
		{
			Node * temp = this->top;
			while (temp != NULL)
			{
				cout << " " << temp->data;
				temp = temp->next;
			}
		}
		cout << "\n";
	}
	//Add a new element in stack
	void push(int data)
	{
		//Make a new stack node
		Node * new_node = new Node(data);
		if (new_node != NULL)
		{
			new_node->next = this->top;
			this->top = new_node;
		}
		else
		{
			cout << "Memory overflow\n";
		}
	}
	//Add a top element in stack
	//When stack is empty it returns -1
	int pop()
	{
		int temp = -1;
		if (this->top != NULL)
		{
			temp = this->top->data;
			this->top = this->top->next;
		}
		return temp;
	}
	bool is_empty()
	{
		if (this->top != NULL)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	//Used to get top element of stack
	int peek()
	{
		if (this->top != NULL)
		{
			return this->top->data;
		}
		else
		{
			return -1;
		}
	}
	//Sort array element by using stack
	void sort_array(int arr[], int size)
	{
		if (size <= 0)
		{
			return;
		}
		int temp = 0, j = 0, k = 0;
		for (int i = 0; i < size; ++i)
		{
			if (this->is_empty() || this->peek() <= arr[i])
			{
				//Add array element into stack when stack is empty, 
				//or array element is greater than equal to top of stack
				this->push(arr[i]);
			}
			else
			{
				j = i;
				temp = arr[j];
				//When array element is less than stack top element
				//Then insert new element in its proper position
				while (!this->is_empty() && this->peek() > temp)
				{
					//use array space and assign the stack element 
					//until stack top is not null or its value 
					//is less than current array element
					arr[j] = this->pop();
					j--;
				}
				//assign current element
				arr[j] = temp;
				//After that  array elements between given index is add to stack
				for (k = j; k <= i; k++)
				{
					this->push(arr[k]);
				}
			}
		}
		//Assign the sorted value in actual array
		for (int i = size - 1; i >= 0; --i)
		{
			arr[i] = this->pop();
		}
	}
	//Display array elements
	void display(int arr[], int size)
	{
		for (int i = 0; i < size; ++i)
		{
			cout << " " << arr[i];
		}
		cout << "\n";
	}
};
int main()
{
	MyStack obj = MyStack();
	int arr[] = {
		6,
		1,
		0,
		5,
		-2,
		8,
		2,
		3,
		6,
		-3,
		62,
		21
	};
	//Get the size of array
	int size = sizeof(arr) / sizeof(arr[0]);
	obj.display(arr, size);
	obj.sort_array(arr, size);
	obj.display(arr, size);
	return 0;
}

 6 1 0 5 -2 8 2 3 6 -3 62 21
 -3 -2 0 1 2 3 5 6 6 8 21 62

/*
  C# Program
  Sort array using stack
*/
//Stack Node
using System;
class Node
{
	public int data;
	public Node next;
	public Node(int data)
	{
		this.data = data;
		this.next = null;
	}
}
class MyStack
{
	public Node top;
	public MyStack()
	{
		top = null;
	}
	public void display()
	{
		if (top != null)
		{
			Node temp = top;
			while (temp != null)
			{
				Console.Write(" " + temp.data);
				temp = temp.next;
			}
		}
		Console.Write("\n");
	}
	//Add a new element in stack
	public void push(int data)
	{
		//Make a new stack node
		Node new_node = new Node(data);
		if (new_node != null)
		{
			new_node.next = top;
			top = new_node;
		}
		else
		{
			Console.Write("Memory overflow\n");
		}
	}
	//Add a top element in stack
	//When stack is empty it returns -1
	public int pop()
	{
		int temp = -1;
		if (top != null)
		{
			temp = top.data;
			top = top.next;
		}
		return temp;
	}
	public Boolean is_empty()
	{
		if (this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	//Used to get top element of stack
	public int peek()
	{
		if (top != null)
		{
			return top.data;
		}
		else
		{
			return -1;
		}
	}
	//Sort array element by using stack
	public void sort_array(int[] arr, int size)
	{
		if (size <= 0)
		{
			return;
		}
		int temp = 0, j = 0, k = 0;
		for (int i = 0; i < size; i++)
		{
			if (this.is_empty() || this.peek() <= arr[i])
			{
				//Add array element into stack when stack is empty, 
				//or array element is greater than equal to top of stack
				this.push(arr[i]);
			}
			else
			{
				j = i;
				temp = arr[j];
				//When array element is less than stack top element
				//Then insert new element in its proper position
				while (!this.is_empty() && this.peek() > temp)
				{
					//use array space and assign the stack element 
					//until stack top is not null or its value 
					//is less than current array element
					arr[j] = this.pop();
					j--;
				}
				//assign current element
				arr[j] = temp;
				//After that  array elements between given index is add to stack
				for (k = j; k <= i; k++)
				{
					this.push(arr[k]);
				}
			}
		}
		//Assign the sorted value in actual array
		for (int i = size - 1; i >= 0; i--)
		{
			arr[i] = this.pop();
		}
	}
	//Display array elements
	public void display(int[] arr, int size)
	{
		for (int i = 0; i < size; i++)
		{
			Console.Write(" " + arr[i]);
		}
		Console.Write("\n");
	}
	public static void Main(String[] args)
	{
		MyStack obj = new MyStack();
		int[] arr = {
			6,
			1,
			0,
			5,
			-2,
			8,
			2,
			3,
			6,
			-3,
			62,
			21
		};
		//Get the size of array
		int size = arr.Length;
		obj.display(arr, size);
		obj.sort_array(arr, size);
		obj.display(arr, size);
	}
}

 6 1 0 5 -2 8 2 3 6 -3 62 21
 -3 -2 0 1 2 3 5 6 6 8 21 62

<?php
/*
  Php Program
  Sort array using stack
*/
//Stack Node
class Node
{
	public $data;
	public $next;

	function __construct($data)
	{
		$this->data = $data;
		$this->next = null;
	}
}
class MyStack
{
	public $top;

	function __construct()
	{
		$this->top = null;
	}
	//Add a new element in stack
	public 	function push($data)
	{
		//Make a new stack node
		$new_node = new Node($data);
		if ($new_node != null)
		{
			$new_node->next = $this->top;
			$this->top = $new_node;
		}
		else
		{
			echo("Memory overflow\n");
		}
	}
	//Add a top element in stack
	//When stack is empty it returns -1
	public 	function pop()
	{
		$temp = -1;
		if ($this->top != null)
		{
			$temp = $this->top->data;
			$this->top = $this->top->next;
		}
		return $temp;
	}
	public 	function is_empty()
	{
		if ($this->top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	//Used to get top element of stack
	public 	function peek()
	{
		if ($this->top != null)
		{
			return $this->top->data;
		}
		else
		{
			return -1;
		}
	}
	//Sort array element by using stack
	public 	function sort_array( & $arr, $size)
	{
		if ($size <= 0)
		{
			return;
		}
		$temp = 0;
		$j = 0;
		$k = 0;
		for ($i = 0; $i < $size; ++$i)
		{
			if ($this->is_empty() || $this->peek() <= $arr[$i])
			{
				//Add array element into stack when stack is empty, 
				//or array element is greater than equal to top of stack
				$this->push($arr[$i]);
			}
			else
			{
				$j = $i;
				$temp = $arr[$j];
				//When array element is less than stack top element
				//Then insert new element in its proper position
				while (!$this->is_empty() && $this->peek() > $temp)
				{
					//use array space and assign the stack element 
					//until stack top is not null or its value 
					//is less than current array element
					$arr[$j] = $this->pop();
					$j--;
				}
				//assign current element
				$arr[$j] = $temp;
				//After that  array elements between given index is add to stack
				for ($k = $j; $k <= $i; $k++)
				{
					$this->push($arr[$k]);
				}
			}
		}
		//Assign the sorted value in actual array
		for ($i = $size - 1; $i >= 0; --$i)
		{
			$arr[$i] = $this->pop();
		}
	}
	//Display array elements
	public 	function display( & $arr, $size)
	{
		for ($i = 0; $i < $size; ++$i)
		{
			echo(" ". $arr[$i]);
		}
		echo("\n");
	}
}

function main()
{
	$obj = new MyStack();
	//Define the element of unsorted array
	$arr = array(6, 1, 0, 5, -2, 8, 2, 3, 6, -3, 62, 21);
	//Get the size of array
	$size = count($arr);
	$obj->display($arr, $size);
	$obj->sort_array($arr, $size);
	$obj->display($arr, $size);
}
main();

 6 1 0 5 -2 8 2 3 6 -3 62 21
 -3 -2 0 1 2 3 5 6 6 8 21 62

/*
  Node Js Program
  Sort array using stack
*/
//Stack Node
class Node
{
	constructor(data)
	{
		this.data = data;
		this.next = null;
	}
}
class MyStack
{
	constructor()
	{
		this.top = null;
	}
	//Add a new element in stack
	push(data)
	{
		//Make a new stack node
		var new_node = new Node(data);
		if (new_node != null)
		{
			new_node.next = this.top;
			this.top = new_node;
		}
		else
		{
			process.stdout.write("Memory overflow\n");
		}
	}
	//Add a top element in stack
	//When stack is empty it returns -1
	pop()
	{
		var temp = -1;
		if (this.top != null)
		{
			temp = this.top.data;
			this.top = this.top.next;
		}
		return temp;
	}
	is_empty()
	{
		if (this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	//Used to get top element of stack
	peek()
	{
		if (this.top != null)
		{
			return this.top.data;
		}
		else
		{
			return -1;
		}
	}
	//Sort array element by using stack
	sort_array(arr, size)
	{
		if (size <= 0)
		{
			return;
		}
		var temp = 0;
		var j = 0;
		var k = 0;
		for (var i = 0; i < size; ++i)
		{
			if (this.is_empty() || this.peek() <= arr[i])
			{
				//Add array element into stack when stack is empty, 
				//or array element is greater than equal to top of stack
				this.push(arr[i]);
			}
			else
			{
				j = i;
				temp = arr[j];
				//When array element is less than stack top element
				//Then insert new element in its proper position
				while (!this.is_empty() && this.peek() > temp)
				{
					//use array space and assign the stack element 
					//until stack top is not null or its value 
					//is less than current array element
					arr[j] = this.pop();
					j--;
				}
				//assign current element
				arr[j] = temp;
				//After that  array elements between given index is add to stack
				for (k = j; k <= i; k++)
				{
					this.push(arr[k]);
				}
			}
		}
		//Assign the sorted value in actual array
		for (var i = size - 1; i >= 0; --i)
		{
			arr[i] = this.pop();
		}
	}
	//Display array elements
	display(arr, size)
	{
		for (var i = 0; i < size; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
		process.stdout.write("\n");
	}
}

function main(args)
{
	var obj = new MyStack();
	//Define the element of unsorted array
	var arr = [6, 1, 0, 5, -2, 8, 2, 3, 6, -3, 62, 21];
	//Get the size of array
	var size = arr.length;
	obj.display(arr, size);
	obj.sort_array(arr, size);
	obj.display(arr, size);
}
main();

 6 1 0 5 -2 8 2 3 6 -3 62 21
 -3 -2 0 1 2 3 5 6 6 8 21 62

#   Python 3 Program
#   Sort array using stack

# Stack Node
class Node :
	
	def __init__(self, data) :
		self.data = data
		self.next = None
	

class MyStack :
	
	def __init__(self) :
		self.top = None
	
	# Add a new element in stack
	def push(self, data) :
		# Make a new stack node
		new_node = Node(data)
		if (new_node != None) :
			new_node.next = self.top
			self.top = new_node
		else :
			print("Memory overflow\n", end = "")
		
	
	# Add a top element in stack
	# When stack is empty it returns -1
	def pop(self) :
		temp = -1
		if (self.top != None) :
			temp = self.top.data
			self.top = self.top.next
		
		return temp
	
	def is_empty(self) :
		if (self.top != None) :
			return False
		else :
			return True
		
	
	# Used to get top element of stack
	def peek(self) :
		if (self.top != None) :
			return self.top.data
		else :
			return -1
		
	
	# Sort array element by using stack
	def sort_array(self, arr, size) :
		if (size <= 0) :
			return
		
		temp = 0
		j = 0
		k = 0
		i = 0
		while (i < size) :
			if (self.is_empty() or self.peek() <= arr[i]) :
				# Add array element into stack when stack is empty, 
				# or array element is greater than equal to top of stack
				self.push(arr[i])
			else :
				j = i
				temp = arr[j]
				# When array element is less than stack top element
				# Then insert new element in its proper position
				while (not self.is_empty() and self.peek() > temp) :
					# use array space and assign the stack element 
					# until stack top is not null or its value 
					# is less than current array element
					arr[j] = self.pop()
					j -= 1
				
				# assign current element
				arr[j] = temp
				# After that  array elements between given index is add to stack
				k = j
				while (k <= i) :
					self.push(arr[k])
					k += 1
				
			
			i += 1
		
		# Assign the sorted value in actual array
		i = size - 1
		while (i >= 0) :
			arr[i] = self.pop()
			i -= 1
		
	
	# Display array elements
	def display(self, arr, size) :
		i = 0
		while (i < size) :
			print(" ", arr[i], end = "")
			i += 1
		
		print("\n", end = "")
	

def main() :
	obj = MyStack()
	arr = [6, 1, 0, 5, -2, 8, 2, 3, 6, -3, 62, 21]
	# Get the size of array
	size = len(arr)
	obj.display(arr, size)
	obj.sort_array(arr, size)
	obj.display(arr, size)


if __name__ == "__main__": main()

  6  1  0  5  -2  8  2  3  6  -3  62  21
  -3  -2  0  1  2  3  5  6  6  8  21  62

#   Ruby Program
#   Sort array using stack

# Stack Node
class Node

	# Define the accessor and reader of class Node
	attr_reader :data, :next
	attr_accessor :data, :next

	def initialize(data)
	
		self.data = data
		self.next = nil
	end
end
class MyStack

	# Define the accessor and reader of class MyStack
	attr_reader :top
	attr_accessor :top
	
	def initialize()
	
		@top = nil
	end
	# Add a new element in stack
	def push(data)
	
		# Make a new stack node
		new_node = Node.new(data)
		if (new_node != nil)
		
			new_node.next = @top
			@top = new_node
		else
		
			print("Memory overflow\n")
		end
	end
	# Add a top element in stack
	# When stack is empty it returns -1
	def pop()
	
		temp = -1
		if (@top != nil)
		
			temp = @top.data
			@top = @top.next
		end
		return temp
	end
	def is_empty()
	
		if (self.top != nil)
		
			return false
		else
		
			return true
		end
	end
	# Used to get top element of stack
	def peek()
	
		if (@top != nil)
		
			return @top.data
		else
		
			return -1
		end
	end
	# Sort array element by using stack
	def sort_array(arr, size)
	
		if (size <= 0)
		
			return
		end
		temp = 0
		j = 0
		k = 0
		i = 0
		while (i < size)
		
			if (self.is_empty() || self.peek() <= arr[i])
			
				# Add array element into stack when stack is empty, 
				# or array element is greater than equal to top of stack
				self.push(arr[i])
			else
			
				j = i
				temp = arr[j]
				# When array element is less than stack top element
				# Then insert new element in its proper position
				while (!self.is_empty() && self.peek() > temp)
				
					# use array space and assign the stack element 
					# until stack top is not null or its value 
					# is less than current array element
					arr[j] = self.pop()
					j -= 1
				end
				# assign current element
				arr[j] = temp
				# After that  array elements between given index is add to stack
				k = j
				while (k <= i)
				
					self.push(arr[k])
					k += 1
				end
			end
			i += 1
		end
		# Assign the sorted value in actual array
		i = size - 1
		while (i >= 0)
		
			arr[i] = self.pop()
			i -= 1
		end
	end
	# Display array elements
	def display(arr, size)
	
		i = 0
		while (i < size)
		
			print("  ", arr[i])
			i += 1
		end
		print("\n")
	end
end
def main()

	obj = MyStack.new()
	arr = [6, 1, 0, 5, -2, 8, 2, 3, 6, -3, 62, 21]
	# Get the size of array
	size = arr.length
	obj.display(arr, size)
	obj.sort_array(arr, size)
	obj.display(arr, size)
end
main()

  6  1  0  5  -2  8  2  3  6  -3  62  21
  -3  -2  0  1  2  3  5  6  6  8  21  62

/*
  Scala Program
  Sort array using stack
*/
//Stack Node
class Node(var data: Int,
	var next: Node)
{
	def this(data: Int)
	{
		this(data,null);
	}
}
class MyStack(var top: Node)
{
	def this()
	{
		this(null);
	}
	//Add a new element in stack
	def push(data: Int): Unit = {
		//Make a new stack node
		var new_node: Node = new Node(data);
		if (new_node != null)
		{
			new_node.next = top;
			top = new_node;
		}
		else
		{
			print("Memory overflow\n");
		}
	}
	//Add a top element in stack
	//When stack is empty it returns -1
	def pop(): Int = {
		var temp: Int = -1;
		if (top != null)
		{
			temp = top.data;
			top = top.next;
		}
		return temp;
	}
	def is_empty(): Boolean = {
		if (this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	//Used to get top element of stack
	def peek(): Int = {
		if (top != null)
		{
			return top.data;
		}
		else
		{
			return -1;
		}
	}
	//Sort array element by using stack
	def sort_array(arr: Array[Int], size: Int): Unit = {
		if (size <= 0)
		{
			return;
		}
		var temp: Int = 0;
		var j: Int = 0;
		var k: Int = 0;
		var i: Int = 0;
		while (i < size)
		{
			if (this.is_empty() || this.peek() <= arr(i))
			{
				//Add array element into stack when stack is empty, 
				//or array element is greater than equal to top of stack
				this.push(arr(i));
			}
			else
			{
				j = i;
				temp = arr(j);
				//When array element is less than stack top element
				//Then insert new element in its proper position
				while (!this.is_empty() && this.peek() > temp)
				{
					//use array space and assign the stack element 
					//until stack top is not null or its value 
					//is less than current array element
					arr(j) = this.pop();
					j -= 1;
				}
				//assign current element
				arr(j) = temp;
				//After that  array elements between given index is add to stack
				k = j;
				while (k <= i)
				{
					this.push(arr(k));
					k += 1;
				}
			}
			i += 1;
		}
		//Assign the sorted value in actual array
		i = size - 1;
		while (i >= 0)
		{
			arr(i) = this.pop();
			i -= 1;
		}
	}
	//Display array elements
	def display(arr: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		while (i < size)
		{
			print("  " + arr(i));
			i += 1;
		}
		print("\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MyStack = new MyStack();
		var arr: Array[Int] = Array(6, 1, 0, 5, -2, 8, 2, 3, 6, -3, 62, 21);
		//Get the size of array
		var size: Int = arr.length;
		obj.display(arr, size);
		obj.sort_array(arr, size);
		obj.display(arr, size);
	}
}

  6  1  0  5  -2  8  2  3  6  -3  62  21
  -3  -2  0  1  2  3  5  6  6  8  21  62

/*
  Swift Program
  Sort array using stack
*/
//Stack Node
class Node
{
	var data: Int;
	var next: Node? ;
	init(_ data: Int)
	{
		self.data = data;
		self.next = nil;
	}
}
class MyStack
{
	var top: Node? ;
	init()
	{
		self.top = nil;
	}
	//Add a new element in stack
	func push(_ data: Int)
	{
		//Make a new stack node
		let new_node: Node? = Node(data);
		if (new_node != nil)
		{
			new_node!.next = self.top;
			self.top = new_node;
		}
		else
		{
			print("Memory overflow\n", terminator: "");
		}
	}
	//Add a top element in stack
	//When stack is empty it returns -1
	func pop() -> Int
	{
		var temp: Int = -1;
		if (self.top != nil)
		{
			temp = self.top!.data;
			self.top = self.top!.next;
		}
		return temp;
	}
	func is_empty() -> Bool
	{
		if (self.top != nil)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	//Used to get top element of stack
	func peek() -> Int
	{
		if (self.top != nil)
		{
			return self.top!.data;
		}
		else
		{
			return -1;
		}
	}
	//Sort array element by using stack
	func sort_array(_ arr: inout[Int], _ size: Int)
	{
		if (size <= 0)
		{
			return;
		}
		var temp: Int = 0;
		var j: Int = 0;
		var k: Int = 0;
		var i: Int = 0;
		while (i < size)
		{
			if (self.is_empty() || self.peek() <= arr[i])
			{
				//Add array element into stack when stack is empty, 
				//or array element is greater than equal to top of stack
				self.push(arr[i]);
			}
			else
			{
				j = i;
				temp = arr[j];
				//When array element is less than stack top element
				//Then insert new element in its proper position
				while (!self.is_empty() && self.peek() > temp)
				{
					//use array space and assign the stack element 
					//until stack top is not null or its value 
					//is less than current array element
					arr[j] = self.pop();
					j -= 1;
				}
				//assign current element
				arr[j] = temp;
				//After that  array elements between given index is add to stack
				k = j;
				while (k <= i)
				{
					self.push(arr[k]);
					k += 1;
				}
			}
			i += 1;
		}
		//Assign the sorted value in actual array
		i = size - 1;
		while (i >= 0)
		{
			arr[i] = self.pop();
			i -= 1;
		}
	}
	//Display array elements
	func display(_ arr: [Int], _ size: Int)
	{
		var i: Int = 0;
		while (i < size)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
		print("\n", terminator: "");
	}
}
func main()
{
	let obj: MyStack = MyStack();
	var arr: [Int] = [6, 1, 0, 5, -2, 8, 2, 3, 6, -3, 62, 21];
	//Get the size of array
	let size: Int = arr.count;
	obj.display(arr, size);
	obj.sort_array(&arr, size);
	obj.display(arr, size);
}
main();

  6  1  0  5  -2  8  2  3  6  -3  62  21
  -3  -2  0  1  2  3  5  6  6  8  21  62

Time Complexity

The time complexity of the algorithm is O(n^2) in the worst case, where n is the size of the input array. This is because in the worst case, all elements are pushed and popped from the stack, which takes O(n) time in each iteration.

Resultant Output Explanation

For the given example array:

int arr[] = {6, 1, 0, 5, -2, 8, 2, 3, 6, -3, 62, 21};

The output shows the sorted array in non-decreasing order:

-3  -2  0  1  2  3  5  6  6  8  21  62

The output demonstrates that the array has been successfully sorted using the stack-based sorting algorithm.