Interviewer may ask you this question if you have more than 3 years of experience in java development. So lets have a look, how to sort a stack using merge sort?

Lets see sample input and output for better understanding:

Algorithm
For this we will follow these below two steps,
1. Break the stack into two parts by using two temporary stack.

2. When only one element remains on a Stack, Merge it.

Lets have a look on the program,

package com.codebyakram;
 
import java.util.Stack;
 
public class SortStack {
 
    public static void main(String args[]) {
        Stack stack = new Stack();
        stack.push(5);
        stack.push(9);
        stack.push(4);
        stack.push(1);
        stack.push(2);
        stack.push(-1);

 
        sort(stack);
 
        System.out.println(stack);
    }
 
    private static void sort(Stack stack) {
        Stack s1 = new Stack();
        Stack s2 = new Stack();
 
        while (stack.size() != 0) {
            if (stack.size() % 2 == 0) {
                s1.push(stack.pop());
            } else {
                s2.push(stack.pop());
            }
        }
 
        if (s1.size() > 1) {
            sort(s1);
        }
 
        if (s2.size() > 1) {
            sort(s2);
        }
 
        merge(s1, s2, stack);
    }
 
    private static void merge(Stack s1, Stack s2, Stack stack) {
        Stack mergedStack = new Stack();
        while (!s1.isEmpty() && !s2.isEmpty()) {
            if ((Integer) s1.peek() < (Integer) s2.peek()) {
                mergedStack.push(s2.pop());
            } else {
                mergedStack.push(s1.pop());
            }
        }
 
        while (!s1.isEmpty()) {
            mergedStack.push(s1.pop());
        }
 
        while (!s2.isEmpty()) {
            mergedStack.push(s2.pop());
        }
 
        while (!mergedStack.isEmpty()) {
            stack.push(mergedStack.pop());
        }
    }
}

An adjacency list represents a graph as an array of linked list.

The index of the array represents a vertex and each element in its linked list represents the other vertices that form an edge with the vertex.

Adjacency List representation
A graph and its equivalent adjacency list representation is shown below.

An adjacency list is efficient in terms of storage because we only need to store the values for the edges. For a sparse graph with millions of vertices and edges, this can mean a lot of saved space.

Adjacency List Structure
The simplest adjacency list needs a node data structure to store a vertex and a graph data structure to organize the nodes.


We stay close to the basic definition of graph - a collection of vertices and edges {V, E}. For simplicity we use an unlabeled graph as opposed to a labeled one i.e. the vertexes are identified by their indices 0,1,2,3.

Let's dig into the data structures.

struct node
{
    int vertex;
    struct node* next;
};
struct Graph
{
    int numVertices;
    struct node** adjLists;
};

Don't let the struct node** adjLists overwhelm you.

All we are saying is we want to store a pointer to struct node*. This is because we don't know how many vertices the graph will have and so we cannot create an array of Linked Lists at compile time.

Adjacency List Java
We use Java Collections to store the Array of Linked Lists.

class Graph
{
    private int numVertices;
    private LinkedList adjLists[];
}

The type of LinkedList is determined what data you want to store in it. For a labeled graph, you could store a dictionary instead of an Integer

Adjacency List code Java

import java.io.*;
import java.util.*;
class Graph
{
    private int numVertices;
    private LinkedList adjLists[];
 
    Graph(int vertices)
    {
        numVertices = vertices;
        adjLists = new LinkedList[vertices];
        
        for (int i = 0; i < vertices; i++)
            adjLists[i] = new LinkedList();
    }
 
    void addEdge(int src, int dest)
    {
        adjLists[src].add(dest);
    }
 
    public static void main(String args[])
    {
        Graph g = new Graph(4);
 
         g.addEdge(0, 1);
         g.addEdge(0, 2);
         g.addEdge(1, 2);
         g.addEdge(2, 3);
    }
}

Traversal meaning visiting all the nodes of a graph. Breadth first Search is also known as Breadth first traversal and is a recursive algorithm for searching all the nodes of a graph or tree data structure.

BFS algorithm
A standard BFS algorithm implementation puts each nodes of the graph or tree into one of two categories:
Visited and
Not Visited

The purpose of the algorithm is to mark each node as visited while avoiding cycles.

The algorithm works as follows:

1. Start by putting any one of the graph's node at the back of a queue or array.
2. Take the front node of the queue and add it to the visited list.
3. Create a list of that node's adjacent nodes. Add the ones which aren't in the visited list to the back of the queue.
4. Keep repeating steps 2 and 3 until the queue is empty.

The graph might have two different disconnected parts so to make sure that we cover every node, we can also run the BFS algorithm on every node

BFS example
Let's see how the BFS algorithm works with an example. We use an undirected graph with 5 nodes.

We start from node 0, the BFS algorithm starts by putting it in the Visited list and putting all its adjacent nodes in the queue.

Next, we visit the element at the front of queue i.e. 1 and go to its adjacent nodes. Since 0 has already been visited, we visit 2 instead.

Node 2 has an unvisited adjacent node in 4, so we add that to the back of the queue and visit 3, which is at the front of the queue.

Only 4 remains in the queue since the only adjacent node of 3 i.e. 0 is already visited. We visit it.

Since the queue is empty, we have completed the Depth First Traversal of the graph.

BFS pseudocode

create a queue Q 
mark v as visited and put v into Q 
while Q is non-empty 
    remove the head u of Q 
    mark and enqueue all (unvisited) neighbours of u

BFS Java code

import java.io.*;
import java.util.*;
 
class Graph
{
    private int numVertices;
    private LinkedList adjLists[];
    private boolean visited[];
 
    Graph(int v)
    {
        numVertices = v;
        visited = new boolean[numVertices];
        adjLists = new LinkedList[numVertices];
        for (int i=0; i i = adjLists[currVertex].listIterator();
            while (i.hasNext())
            {
                int adjVertex = i.next();
                if (!visited[adjVertex])
                {
                    visited[adjVertex] = true;
                    queue.add(adjVertex);
                }
            }
        }
    }
 
    public static void main(String args[])
    {
        Graph g = new Graph(4);
 
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
 
        System.out.println("Following is Breadth First Traversal "+
                           "(starting from vertex 2)");
 
        g.BFS(2);
    }
}

Traversal meaning visiting all the nodes of a given graph. Depth first Search is also know as Depth first traversal. DFS is a recursive algorithm for searching all the vertices of a graph or tree.

DFS algorithm
A standard DFS implementation puts each vertex of the graph into one of two categories:

1.Visited
2. Not Visited

The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.

The DFS algorithm works as follows:

1. Start by putting any one of the graph's vertices on top of a stack.
2. Take the top item of the stack and add it to the visited list.
3. Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to the top of stack.
4. Keep repeating steps 2 and 3 until the stack is empty.

DFS example
Let's see how the Depth First Search algorithm works with an example. We use an undirected graph with 5 vertices.

We start from node 0, the DFS algorithm starts by putting it in the Visited list and putting all its adjacent nodes in the stack.

Next, we visit the element at the top of stack i.e. 1 and go to its adjacent nodes. Since 0 has already been visited, we visit 2 instead.

Node 2 has an unvisited adjacent node in 4, so we add that to the top of the stack and visit it.

After we visit the last element 3, it doesn't have any unvisited adjacent nodes, so we have completed the Depth First Traversal of the graph.

DFS pseudocode (recursive implementation)
The pseudocode for Depth first Search is shown below. In the init() function, notice that we run the DFS function on every node. This is because the graph might have two different disconnected parts so to make sure that we cover every vertex, we can also run the DFS algorithm on every node.

DFS(G, u)
    u.visited = true
    for each v ∈ G.Adj[u]
        if v.visited == false
            DFS(G,v)
     
init() {
    For each u ∈ G
        u.visited = false
     For each u ∈ G
       DFS(G, u)
}

DFS Java code

import java.io.*;
import java.util.*;
 
class Graph
{
    private int numVertices;
    private LinkedList adjLists[];
    private boolean visited[];
 
    Graph(int vertices)
    {
        numVertices = vertices;
        adjLists = new LinkedList[vertices];
        visited = new boolean[vertices];
        
        for (int i = 0; i < vertices; i++)
            adjLists[i] = new LinkedList();
    }
 
    void addEdge(int src, int dest)
    {
        adjLists[src].add(dest);
    }
 
    void DFS(int vertex)
    {
        visited[vertex] = true;
        System.out.print(vertex + " ");
 
        Iterator ite = adjLists[vertex].listIterator();
        while (ite.hasNext())
        {
            int adj = ite.next();
            if (!visited[adj])
                DFS(adj);
        }
    }
 
 
    public static void main(String args[])
    {
        Graph g = new Graph(4);
 
         g.addEdge(0, 1);
         g.addEdge(0, 2);
         g.addEdge(1, 2);
         g.addEdge(2, 3);
 
        System.out.println("Following is Depth First Traversal");
 
        g.DFS(2);
    }
}

Before looking into Heap Sort, let's understand what is Heap and how it helps in sorting.
What is Complete Binary Tree?
A Complete binary tree is a binary tree in which every node other than the leaves has two children. In complete binary tree at every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Let's understand with simple words now,
If a Binary Tree is filled level by level, left to right (Left child followed by Right child.) then it is called complete binary tree.

If Right child is present without Left child then it is not complete.

What is Heap property in Binary Tree?

 A binary Tree is said to follow a heap property if tree is complete binary tree and every element of the tree is Larger (or Smaller) than any of its descendants if they exists.

Depending on the ordering, a heap is called a max-heap or a min-heap.
In a Max-heap, the keys of parent nodes are always greater than or  equal to those of the children.
In max-heap, Largest element of the Tree is always at top(Root Node).

In a Min-heap, the keys of parent nodes are less than or equal to those of the children.
In min-heap, Smallest element of the Tree is always at top(Root Node).

Important aspects of Heap sort. (Prerequisites)
Before going into Heapsort algorithm, Let's understand few points,

If we have an array say [4, 10, 3, 5, 1], then we can represent array as complete binary tree
(start adding nodes from left to right) like shown below.

Each element has left and right child present in array except for leaf nodes, but how to find left and right child of non-leaf nodes in array.

We will get left and right child of non leaf elements using formula,
Left child index   = 2 * (index of root, whose left and right child to find) + 1
Right child index = 2 * (index of root, whose left and right child to find) + 1

Left child and Right child of element at index 0 (element 4) is,
Left child index  = 2 * i + 1   = 2 * 0 + 1   = 1
Right child index = 2 * i + 2   = 2 * 0 + 2   = 2

Left child and Right child of element at index 1 (element 10) is,
Left child index  = 2 * i + 1   = 2 * 1 + 1   = 3
Right child index = 2 * i + 2   = 2 * 1 + 2   = 4

Left child and Right child of element at index 2 (element 3) is,
Left child index  = 2 * i + 1   = 2 * 2 + 1   = 5
(index 5 is greater than length of array, so element 3 has no left child)

Right child index = 2 * i + 2   = 2 * 2 + 2   = 6
(index 6 is greater than length of array, so element 3 has no right child)

Algorithm
STEP 1:  Logically, think the given array as Complete Binary Tree,

STEP 2:  For sorting the array in ascending order, check whether the tree is satisfying Max-heap
               property at each node,
               (For descending order, Check whether the tree is satisfying Min-heap property)
               Here we will be sorting in Ascending order,

STEP 3: If the tree is satisfying Max-heap property, then largest item is stored at the root of the heap.
               (At this point we have found the largest element in array, Now if we place this element at
               the end(nth position) of the array then 1 item in array is at proper place.)
               We will remove the largest element from the heap and put at its proper place(nth position) in
               array.
 
              After removing the largest element, which element will take its place? 
              We will put last element of the heap at the vacant place. After placing the last element at the
              root, The new tree formed may or may not satisfy max-heap property.
              So, If it is not satisfying max-heap property then first task is to make changes to the tree, So
              that it satisfies max-heap property.
         
              (Heapify process: The process of making changes to tree so that it satisfies max-heap
               property is called heapify)

              When tree satisfies max-heap property, again largest item is stored at the root of the heap. 
              We will remove the largest element from the heap and put at its proper place(n-1 position) in
              array.
 
              Repeat step 3 until size of array is 1 (At this point all elements are sorted.)

Heapify Process with Example
Heapify process checks whether item at parent nodes has larger value than its left and right child.

If parent node is not largest compared to its left and right child, then it finds the largest item among parent, its left and right child and replaces largest with parent node.

It repeat the process for each node and at one point tree will start satisfying max-heap property.
At this point, stop heapify process and largest element will be at root node.

We found the largest element, Remove it and put it at its proper place in array,
Put the last element of the tree at the place we removed the node(that is at root of the tree)
Placing last node at the root may disturbed the max-heap property of root node.
So again repeat the Heapify process for root node. Continue heapify process until all nodes in tree satisfy max-heap property.


Initially, From which node we will start heapify process? Do we need to check each and every node that they satisfy heap property?
We do not have to look into leaf nodes as they don't have children and already satisfying max-heap property.
So, we will start looking from the node which has at least one child present.

How we will get that item in array, which has at least one child present?

By using the formula (array.length/2) - 1, we will be able to get the index of the item to start Heapify process. 

 

Lets understand Heapify process with help of an example.

Heap Sort Java Program.

package com.codebyakram.sort;
 
public class HeapSort {
 
    public static void main(String[] args) {
        int[] array = new int[] {4, 10, 3, 5, 1};
 
        new HeapSort().sort(array);
 
        for (int i : array) {
            System.out.print(i + " ");
        }
    }
 
    public void sort(int data[]) {
        int size = data.length;
 
        /*
            {4, 10, 3, 5, 1}
 
                  4
                /  \
               10  3
              / \
             5  1
         */
        //This step is called building a Heap
        for (int i = size / 2 - 1; i >= 0; i--) {
            heapify(i, data, size);
        }
 
        //Once the heap is build by above step, we replace the max element at arr[0](root element) to last index of array
        //and decrease the size by 1 in next iteration as highest element is already at its place.
        for (int i = data.length - 1; i >= 0; i--) {
 
            //Swap max element at root(arr[0] to last element)
            int temp = data[0];
            data[0] = data[i];
            data[i] = temp;
 
            //reduce the heap window by 1
            size = size - 1;
 
            //swapping would have disturbed the heap property,
            //so calling max heapify for index 0 on the reduced heap size.
            //if we pass i in place of size should also work as that also represents the size
            heapify(0, data, size);
        }
    }
 
    private int leftChild(int i) {
        return 2 * i + 1;
    }
 
    private int rightChild(int i) {
        return 2 * i + 2;
    }
 
    private void heapify(int i, int[] data, int size) {
        int largestElementIndex = i;
 
        int leftChildIndex = leftChild(i);
        if (leftChildIndex < size && data[leftChildIndex] > data[largestElementIndex]) {
            largestElementIndex = leftChildIndex;
        }
 
        int rightChildIndex = rightChild(i);
        if (rightChildIndex < size && data[rightChildIndex] > data[largestElementIndex]) {
            largestElementIndex = rightChildIndex;
        }
 
        if (largestElementIndex != i) {
            int swap = data[i];
            data[i] = data[largestElementIndex];
            data[largestElementIndex] = swap;
 
            // Recursively heapify for the affected node
            heapify(largestElementIndex, data, size);
        }
    }
}