Sorting algorithms in Java

Trying to list down some sorting algorithms in Java:

Merge Sort:
It is a divide and conquer algorithm.
Divide the unsorted list into n sub-lists, each containing 1 element (a list of 1 element is considered sorted).

Refer Merge Sort article for details.

Bubble Sort:
Bubble sort is a simple sorting algorithm that works by:

•     Repeatedly going through the list to be sorted
•     Comparing each pair of adjacent items
•     Swapping them if they are in the wrong order

Refer Bubble Sort article for details.

Quick Sort:
Quick sort is based on the principle of divide and conquer.
Quick sort first divides the large lists into two sub smaller lists, the low elements and the high elements.
It can then recursively sort the sub-lists.

Refer Quick Sort article for details.

Insertion Sort
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.

Refer Insertion Sort article for details.

Selection Sort:
Selection sort is a simple algorithm.
It divides the input lists into two parts:

• The sub-list of the items are already sorted, which is built up from left to right at the front(left) of the list.
• The sub-list of the  items remaining to be sorted that occupy the rest of the list.

Refer Selection Sort article for details.

Selection sort in Java

Refer: Main indexed article on sorting.
 
Selection sort is a simple algorithm.

It divides the input lists into two parts:

• The sub-list of the items are already sorted, which is built up from left to right at the front(left) of the list
• The sub-list of the  items remaining to be sorted that occupy the rest of the list.

Initially the sorted sub-list is empty and the unsorted sub-list is the entire input list.
The algorithm proceeds by finding the smallest (or largest depending on the sorting order) element in the unsorted sub-list exchanging it with the leftmost unsorted element (putting in sorted order) and moving the sub-list boundaries one element to the right.

Java code snippet:

Insertion Sort in Java

Refer: Main indexed article on sorting.

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.
It is much less efficient on large lists.

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.
It repeats until no input elements remain.

At each array-position, it checks the value there against the largest value in the sorted list (which happens to be next to it, in the previous array-position checked).
If larger, it leaves the element in place and moves to the next.
If smaller, it finds the correct position within the sorted list, shifts all the larger values up to make a space, and inserts into that correct position.

The diagram below shows the algorithm in 2 parts for better understanding.

Part 1.




Part 2



Java code snippet: