Sort a Stack using Merge Sort

Sort a Stack using Merge Sort.

---

Lets see how to sort a stack using merge sort which uses divide and conquer recursive algorithm.

I recommend reading Merge sort first before proceeding.

Also, check Merge sort article on linked list that will help in understanding Merge sort and this article better.

Lets see sample input and output for better understanding:

Sort a Stack using Merge Sort in Java

Read more

Quick Sort in Java

Quick Sort in Java.

---

Given a unsorted array, Sort it using Quick Sort Algorithm.

Merge sort linked list java

Lets understand what is the input and the expected output.

Read more

Merge sort explanation in java

Merge sort Algorithm in java.

---

Given a unsorted array, Sort it using Merge Sort Algorithm.

Lets understand what is the input and the expected output.

Sort array using merge sort in java

Merge sort Algorithm

---

How Merge Sort works

1. Merge Sort works by breaking the array into 2 equal parts say Left half and Right half.
2. Again break 2 sub array that we got in Step 1 in two equal parts each.  
3. Repeat above steps until only 1 element remains in array because array with only one element is always sorted. 
4. So in each step we are breaking the array in Left half and Right half.  
5. When complete array is divided and contains only Single element in Left and Right half each, Start comparing and sort each Left and Right half, So that portion of array will be sorted.
6. Repeat Step 5 for all the remaining Left and Right sub-array and complete array will be sorted.

Merge sort Time complexity

---

Merge sort time complexity is O(N log N).

Lets understand with the help of below example.

Merge sort algorithm with example

Java program to sort an array using merge sort

---

package com.javabypatel;

public class MergeSort {

    public static void main(String[] args) {
        int arr[] = {10, 1, -2, 8, 9, 10, 1};

        //Before sort
        print(arr);

        mergeSort(arr, 0, arr.length - 1);

        //After sort
        print(arr);
    }

    static void mergeSort(int arr[], int start, int end) {
        if (start >= end)
            return;

        int mid = start + (end - start) / 2;
        mergeSort(arr, start, mid);
        mergeSort(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }

    static void merge(int[] arr, int start, int mid, int end) {
        int i = start;
        int j = mid + 1;
        int counter = 0;

        int[] tempArr = new int[(end - start) + 1];

        while (i <= mid && j <= end) {
            if (arr[j] < arr[i]) {
                tempArr[counter] = arr[j];
                j++;
            } else {
                tempArr[counter] = arr[i];
                i++;
            }
            counter++;
        }
        while (i <= mid) {
            tempArr[counter] = arr[i];
            i++;
            counter++;
        }

        while (j <= end) {
            tempArr[counter] = arr[j];
            j++;
            counter++;
        }

        for (int k = 0; k < counter; k++) {
            arr[start + k] = tempArr[k];
        }
    }

    static void print(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

You may also like to see

---

Sort Linked list using Merge sort

Bubble Sort

Heap Sort

Selection Sort

Insertion Sort

---

How ConcurrentHashMap works and ConcurrentHashMap interview questions

How Much Water Can A Bar Graph with different heights can Hold

Interview Questions-Answer Bank

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.

Read more

Insertion Sort in Java

Insertion Sort in Java

---

Insertion sort is simple sorting algorithm that sorts the complete array by picking one element at a time and shifting it at its right place.

Lets understand above line in more details with the help of an example. Given a array of integers, Sort it using Insertion sort.  

Lets understand what is the input and the expected output.

Read more

Analysis of Heap Sort Time Complexity.

Analysis of Heap Sort Time Complexity.

---

Analysis of Heap Sort Time Complexity. Heap sort worst case, best case and average case time complexity is guaranteed O(n Log n). Heap sort space complexity is O(1). 

Heap Sort Time Complexity

---

1. Heap sort has the best possible worst case running time complexity of O(n Log n).
2. It doesn't need any extra storage and that makes it good for situations where array size is large.

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.

Read more

Analysis of Bubble Sort Time Complexity

Analysis of Bubble Sort Time Complexity.

---

Analysis of Bubble Sort Time Complexity. Bubble sort worst case time complexity is O(n^2), best case is O(n) and average case time complexity is O(n^2). Bubble Sort Java Program.

In this post we will see Bubble sort java program, How Bubble sort works in Java, Bubble sort Algorithm in java and Sorting array using Bubble sort in Java.

Lets understand what is the input and the expected output.

Time Complexity of Bubble Sort Algorithm.

---

1. Time complexity of Bubble sort in Worst Case is O(N^2), which makes it quite inefficient for sorting large data volumes. O(N^2) because it sorts only one item in each iteration and in each iteration it has to compare n-i elements.
2. Time complexity of Bubble sort in Best Case is O(N). When the given data set is already sorted, in that case bubble sort can identify it in one single iteration hence O(N). It means while iterating, from i=0 till arr.length, if there is no swapping required, then the array is already sorted and stop there.
3. Bubble sort can identify when the list is sorted and can stop early.
4. Bubble sort is efficient for (quite) small data sets. 
5. It is Stable sort; i.e., does not change the relative order of elements with equal keys.It takes O(1) extra space.
   

Read more

Why Selection sort is faster than Bubble sort.

Why Selection sort is faster than Bubble sort.

---

Selection sort is faster than Bubble sort because Selection sort swaps elements "n" times in worst case, but Bubble sort swaps almost n*(n-1) times.

Why is Selection sort faster than Bubble sort?

---

Selection sort swaps elements "n" times in worst case, but Bubble sort swaps almost n*(n-1) times.

We all know, Reading time is less than writing time even in-memory. 
(Compare and running time can be ignored)

If we have a system where write operations are extremely expensive and read operations are not, then Selection sort could be ideal.
Selection sort is good for sorting arrays of small size.

Selection sort is better than Bubble sort due to less swapping required.

Note:
In Bubble sort, we can identify whether list is sorted or not in 1st iteration but in Selection sort we can't able to identify that.
Compared to Selection sort, Bubble sort should be used when the given array is almost sorted.

Selection sort Time Complexity Analysis

---

Selecting the lowest element requires scanning all n elements (this takes n - 1 comparisons) and then swapping it into the first position.
 
Finding the next lowest element requires scanning the remaining n - 1 elements and so on, 
= (n - 1) + (n - 2) + ... + 2 + 1 = n(n - 1) / 2 
= O(n^2) comparisons.

Best Case :       O(n)^2 
Worst Case :    O(n)^2 
Average Case : O(n)^2 
Worst Case Space Complexity : O(1) 

Stable : No

Bubble Sort Time Complexity Analysis

---

1. Time complexity of Bubble sort in Worst Case is O(N^2), which makes it quite inefficient for sorting large data volumes. O(N^2) because it sorts only one item in each iteration and in each iteration it has to compare n-i elements.
2. Time complexity of Bubble sort in Best Case is O(N). When the given data set is already sorted, in that case bubble sort can identify it in one single iteration hence O(N). It means while iteratng, from i=0 till arr.length, if there is no swapping required, then the array is already sorted and stop there.
3. Bubble sort can identify when the list is sorted and can stop early.
4. Bubble sort is efficient for (quite) small data sets. 
5. It is Stable sort; i.e., does not change the relative order of elements with equal keys.
6. It takes O(1) extra space.
   

You may also like to see

---

Merge Sort

Heap Sort

Bubble Sort

Insertion Sort

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.

Read more

Analysis of Selection Sort Time Complexity.

Analysis of Selection Sort Time Complexity.

---

Analysis of Selection Sort Time Complexity. Selection sort worst case, best case and average case time complexity is O(n^2). Selection Sort Java Program.

Selection sort Time Complexity Analysis

---

Selecting the lowest element requires scanning all n elements (this takes n - 1 comparisons) and then swapping it into the first position.
 
Finding the next lowest element requires scanning the remaining n - 1 elements and so on, 
= (n - 1) + (n - 2) + ... + 2 + 1 = n(n - 1) / 2 
= O(n^2) comparisons.

Best Case :       O(n)^2 
Worst Case :    O(n)^2 
Average Case : O(n)^2 
Worst Case Space Complexity : O(1) 

Stable : No

Let's start with Selection sort Java program, How Selection sort works in java, Selection sort Algorithm in java. 
 
Sort an array of integers using Selection sort in Java.
Lets understand what is the input and the expected output.
 

Read more

Analysis of Insertion Sort Time Complexity.

Time Complexity of Insertion Sort

---

Insertion sort worst case time complexity is O(n^2), Best case complexity is O(n), Average case complexity is O(n^2). Insertion sort is stable sort and in-place.

Analysis of Insertion Sort Time Complexity.

---

1. The insertion sort, unlike the other sorts, passes through the array only once. 
2. The insertion sort splits an array into two sub-arrays,
    First sub-array on left side is always sorted and increases in size as the sort continues.
    Second sub-array is unsorted, contains all the elements yet to be inserted into the first sub-array, 
    and decreases in size as the sort continues.

3. Insertion sort is efficient for (quite) small data sets.
4. It is more efficient than selection sort or bubble sort.

5. Insertion sort is very efficient for arrays which is nearly(almost) sorted and it sorts nearly sorted 
    array in time complexity of O(N).
    (For sorting an array containing elements in descending order to ascending order, insertion sort 
    will give poor performance and complexity will be O(N^2))

6. It is Stable sort; i.e., does not change the relative order of elements with equal keys.
7. It is In-place sort; i.e., only requires a constant amount O(1) of additional memory space
8. It can sort elements as it receives it and no need of complete data initially before start sorting.
    (Online).

Given a array of integers, Sort it using Insertion sort.  

Lets understand what is the input and the expected output.

Read more

Insertion Sort Algorithm in Java

Insertion Sort Algorithm in Java

---

Insertion sort is popular sorting algorithm. Let's see, how Insertion sort works and Insertion sort Java Program. Insertion sort works by shifting element at its correct position in array.

Given a array of integers, Sort it using Insertion sort.  

Lets understand what is the input and the expected output.

Read more

Bubble Sort Program in Java

Bubble Sort in Java

---

Let's see Bubble sort java program, How Bubble sort works in Java, Bubble sort Algorithm in java.  

Sort array using Bubble sort in Java.
Lets understand what is the input and the expected output.

Read more

Selection Sort in Java

Selection Sort Program in Java

---

Lets understand Selection sort program in java, How Selection sort works in java, Selection sort Algorithm in java. 

Sort an array of integers using Selection sort in Java.
Lets understand what is the input and the expected output.
 

Read more

Bubble Sort

Bubble Sort (Sinking sort)

---

Given a array of integers, Sort it.
Lets understand what is the input and the expected output.

Read more

Insertion Sort

Insertion Sort

---

Given a array of integers, Sort it using Insertion sort. Lets understand what is the input and the expected output.

Read more

Selection Sort

Selection Sort

---

Given a array of integers, Sort it.
Lets understand what is the input and the expected output.

Read more

Sort Linked list using Merge sort.

Sort Linked List using Merge Sort.

---

Given a Linked list, Sort it using Merge Sort Algorithm.

Merge sort is preferred algorithm for sorting a linked list, lets see why,
The way linked list is structured which doesn't allow random access makes some other algorithms like Quicksort perform poorly, So Merge sort is often preferred algorithm for sorting linked list.
 
Lets understand what is the input and the expected output.

Read more

Heap Sort Algorithm

Heap Sort.

---

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.

Read more