---
# System prepended metadata

title: Sorting

---

# Sorting

## Bubble sort
Bubble sort is a simple sorting algorithm that compares adjacent elements of an array and swaps them if the element on the right is smaller than the one on the left. It is an in-place sorting algorithm i.e. no extra space is needed for this sort, the array itself is modified.

<details>
    <summary>Code</summary>
    
```java=
private void sort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        for (int j = i + 1; j < a.length; j++) {
            if (a[i] > a[j]) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
}
```
 
</details>

## Optimised Bubble sort
Same as a bubble sort, but if the input array is already sorted, sorting breaks after the first iterration

<details>
    <summary>Code</summary>
    
```java=
private void sort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        boolean swapped = false;
        for (int j = i + 1; j < a.length; j++) {
            if (a[i] > a[j]) {
                swapped = true;
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
        if (!swapped) {
            break;
        }
    }
}
```
 
</details>

## Quick sort

Quicksort is a sorting algorithm belonging to the divide-and-conquer group of algorithms, and it's an in-place (no need for auxillary data structures), non-stable (doesn't guarantee relative order of same-value elements after sorting) sorting algorithm.

The divide-and-conquer algorithms recursively break down a problem into two or more sub-problems of the same type, making them simpler to solve. The breakdown continues until a problem is simple enough to be solved on it's own (we call this the base case).

In every step of the way an element is placed on the spot it belongs on in the sorted array.


This element is called the pivot. However, if we wanted to use the divide-and-conquer approach and reduce the problem of sorting the array to a smaller group of two sub-arrays we need to abide by the following: while we're placing our pivot at it's spot in the array we need to group the rest of the elements in two smaller groups - the ones left of the pivot are lesser or equal to it, and the ones on the right are bigger than the pivot.

This is actually the key step of the algorithm - called partitioning, and implementing it efficiently is a must if we want our Quicksort to be efficient as well.

Before discussing how Quicksort works, we should address how we choose which element is the pivot. The perfect scenario is that we always choose the element that splits the array in exact halves. However, since this is almost impossible to achieve, we can approach this problem in a few different ways.

For example, the pivot can be the first or the last element in the array (or a sub-array) we're currently processing. We can pick a median element as the pivot, or even choose a random element to play the role.
We have a variety of ways of accomplishing this task, and the approach we'll be taking in this article is to always choose the first (that is, left-most element of the array) as the pivot. Now let's jump into an example and explain how it all works.
![](https://i.imgur.com/6lYZR7I.png)
![](https://i.imgur.com/1Cl7vb5.png)
![](https://i.imgur.com/vaeFJ6Q.png)
![](https://i.imgur.com/Hcng9GA.png)


<details>
    <summary>Code</summary>
    
```java=
private void sort(int[] a, int low, int high) {
    if (low < high) {
        int q = partition(a, low, high);
        sort(a, low, q - 1);
        sort(a, q, high);
    }

}

private int partition(int[] a, int low, int high) {
    int q = low;
    for (int i = low; i < high; i++) {
        if (a[i] <= a[high]) {
            swap(a, i, q++);
        }
    }
    swap(a, high, q);
    return q;
}

private void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}
```
 
</details>

 
## Insert sort
    
Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.
    
![](https://i.imgur.com/4xqa7Ko.png)

<details>
    <summary>Code</summary>
    
```java=
private void sort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {

            a[j + 1] = a[j];
            j = j - 1;
        }
        a[j + 1] = key;
    }
}
```
 
</details>     
 
## Merge sort
    
The merge sort algorithm is based on the principle of divide and conquer algorithm where a problem is divided into multiple sub-problems. Each sub-problem is solved individually and finally, sub-problems are combined to form the final solutions.
    
![](https://i.imgur.com/uee40gi.png)

* Split array into two parts until the part contains 1 item
* When reached the base merge two sorted parts
* Repeat recursively
    
<details>
    <summary>Code</summary>
    
```java=
private void sort(int[] a) {
    mergeSort(a, 0, a.length - 1);
}

private void mergeSort(int[] a, int left, int right) {
    if ( left < right) {
        int m = (right + left) / 2;

        mergeSort(a, left, m);
        mergeSort(a, m + 1, right);
        merge(a, left, m, right);
    }
}

private void merge(int[] a, int left, int m, int right) {

    int nL = m - left + 1;
    int nR = right - m;

    int[] leftArr = new int[nL];

    for (int i = 0; i < nL; i++) {
        leftArr[i] = a[left + i];
    }

    int[] rightArr = new int[nR];

    for (int j = 0; j < nR; j++) {
        rightArr[j] = a[m + 1 + j];
    }

    int i = 0;
    int j = 0;
    int c = left;
    while (i < nL && j < nR) {
        if (leftArr[i] <= rightArr[j]) {
            a[c++] = leftArr[i++];
        } else {
            a[c++] = rightArr[j++];
        }
    }
    while (i < nL) {
        a[c++] = leftArr[i++];
    }
    while (j < nR) {
        a[c++] = rightArr[j++];
    }
}
```
 
</details>     
 
    

## Comparison
    
||||||||
|--- |--- |--- |--- |--- |--- |--- |
|Sort|Average|Best|Worst|Space|Stability|Remarks|
|Bubble sort|O(n^2)|O(n^2)|O(n^2)|Constant|Stable|Always use a modified bubble sort|
|Modified Bubble sort|O(n^2)|O(n)|O(n^2)|Constant|Stable|Stops after reaching a sorted array|
|Selection Sort|O(n^2)|O(n^2)|O(n^2)|Constant|Stable|Even a perfectly sorted input requires scanning the entire array|
|Insertion Sort|O(n^2)|O(n)|O(n^2)|Constant|Stable|In the best case (already sorted), every insert requires constant time|
|Heap Sort|O(n*log(n))|O(n*log(n))|O(n*log(n))|Constant|Instable|By using input array as storage for the heap, it is possible to achieve constant space|
|Merge Sort|O(n*log(n))|O(n*log(n))|O(n*log(n))|Depends|Stable|On arrays, merge sort requires O(n) space; on linked lists, merge sort requires constant space|
|Quicksort|O(n*log(n))|O(n*log(n))|O(n^2)|Constant|Stable|Randomly picking a pivot value (or shuffling the array prior to sorting) can help avoid worst case scenarios such as a perfectly sorted array.|
