Sm0king B!ts
Posts Tags Categories About me
Sm0king B!ts

Contents

Sorting Algos

 included in DSA
   4515 words   22 minutes 
/sorting/sorting.png

Sorting is used to organize data, enable faster searches, generate reports, manage databases, process large datasets.

Note
Use the table of contents to navigate to the portion that you are interested in.

1. Introduction

Sorting is a process of arranging data in a specific order. ususally ascending or descending. It helps to find elements faster. also it organise data for better understanding.

Diff Types of sorting algorithms:

  1. Bubble Sort
  2. Insertion Sort
  3. Selection Sort
  4. Quick Sort
  5. Merge Sort
  6. Heap Sort

1.1 Classification

Sorting algorithms can be broadly classified as:

1. Based on Technique:

  • Comparison Based Sorting.
  • NonComparison Based (Devide and Conquer) Sorting.

2. Based on Behavior:

  • In-place vs Not In-place.
  • Stable vs Unstable.

2. Sorting visualizer

This visualizer gives you the clear understanding of all the sorting algos. How it works internally and how the elements are being compared everything.

3. Bubble sort

Bubble sort is a simple comparison-based sorting algorithm. it repeatedly compares adjacent elements and swap them if they are in the wrong order. In each iteration the largest element bubbles up to the end of the list. You can visualize it above in the visualizer.

3.1 Time & Space Complexity:

Time Complexicity
Best Case: O(n)
Average Case: O(n²)
Worst Case: O(n²)
Space Complexicity
Best Case: O(1)

Pros & Cons:

  • Simple to understand.
  • Inefficient for large datasets.
  • Very slow for large array.

3.2 Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// 1. Bubble sort
void BubbleSort(int *arr, int length)
{
    for (int i = 0; i < length - 1; i++)
    {
        for (int j = 0; j < length - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
Bubble Sort in C++ 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

// Example Use
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    bubbleSort(arr, n);

    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}
Bubble Sort in Js 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

// javascript code
function bubbleSort(arr){
    const n = arr.length;
    for(let i = 0 ; i< n-1 ; i++ ){
        for(let j = 0 ; j< n-i-1 ; j++){
            if(arr[j] > arr[j+1]){
                let temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    return arr;
}

// example use
let arr = [10, 7, 8, 9, 1, 5];

bubbleSort(arr);

console.log(arr);
Bubble Sort in Java 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// java code
public static void bubbleSort(int[] arr){
    int n = arr.length;
    for(int i = 0 ; i< n-1 ; i++ ){
        for(int j = 0 ; j< n-i-1 ; j++){
            if(arr[j] > arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

// example use
public class Main {
    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};

        bubbleSort(arr);

        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}
Bubble Sort in Python 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

# python code
def bubbleSort(arr):
    n = len(arr)
    
    for i in range(n-1):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                # swap
                arr[j] , arr[j+1] = arr[j+1] , arr[j]

    return arr

# Example use
arr = [10, 7, 8, 9, 1, 5]
bubbleSort(arr)
print(arr)

4. Insertion Sort

Insertion Sort is a simple comparison-based sorting algo. it builds the sorted list one element at a time. It works by taking each element and inserting it into its correct postion within the already sorted part of the array.

4.1 Time & Space Complexity:

Time Complexicity
Best Case: O(n)
Average Case: O(n²)
Worst Case: O(n²)
Space Complexicity
Best Case: O(1)

Pros & Cons:

  • Very efficieant for small datasets.
  • Works well for nearly sorted array.
  • O(n²) for large arrays.
  • O(n) when array is already sorted.

4.2 Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// 2. Insertion sort
void InsertionSort(int *arr, int length)
{
    for (int i = 1; i < length; i++)
    {
        int value = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > value)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = value;
    }
}
Insertion Sort in C++ 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int value = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > value) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = value;
    }
}

// Example use
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);

    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}
Insertion Sort in Java 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

// java code
public static void insertionSort(int[] arr){
    int n = arr.length;
    for(int i = 1 ; i< n ; i++ ){
        int value = arr[i];
        int j = i-1;

        while( j>= 0 && arr[j] > value){
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = value;
    }
}

// example use
public class Main {
    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};

        insertionSort(arr);

        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}
Insertion Sort in Js 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// javascript code
function insertionSort(arr){
    const n = arr.length;

    for(let i = 1 ; i< n ; i++ ){
        let value = arr[i];
        let j = i-1;

        while(j >= 0 && arr[j] > value){
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = value;
    }
    return arr;
}

// example use
let arr = [10, 7, 8, 9, 1, 5];

insertionSort(arr);

console.log(arr);
Insertion Sort in Python 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

# python code
def insertionSort(arr):
    n = len(arr)
    
    for i in range(1, n):
        value = arr[i]
        j = i-1

        while j>= 0 and arr[j] > value:
            arr[j+1] = arr[j]
            j -= 1
        
        arr[j+1] = value

    return arr

# Example use
arr = [10, 7, 8, 9, 1, 5]
insertionSort(arr)
print(arr)

5. Selection Sort

Selection Sort is a simple comparison-based sorting algorithm it works by repeatedly selecting the smallest (or largest) element from the unsorted part of the array and placing it at the correct position.It maintains two subarrays. a sorted part and an unsorted part. It is easy to understand and implement.

5.1 Time & Space Complexity:

Time Complexicity
Best Case: O(n²)
Average Case: O(n²)
Worst Case: O(n²)
Space Complexicity
Best Case: O(1)

Pros & Cons:

  • Easy to understand and implement.
  • Unstable in behavior.
  • Inefficient for large datasets.

5.2 Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

void SelectionSort(int *arr, int length)
{
    for (int i = 0; i < length; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < length; j++)
        {
            if (arr[minIndex] > arr[j])
            {
                minIndex = j;
            }
        }
        if (minIndex != i)
        {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}
Selection Sort in C++ 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


#include <iostream>
using namespace std;

// Selection Sort function
void selectionSort(int arr[], int length) {
    for (int i = 0; i < length; i++) {
        int minIndex = i;
        for (int j = i + 1; j < length; j++) {
            if (arr[minIndex] > arr[j]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            swap(arr[i], arr[minIndex]);
        }
    }
}

// Example use
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    selectionSort(arr, n);

    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}
Selection Sort in Java 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

// java code
public static void selectionSort(int[] arr){
    int n = arr.length;
    for(int i = 0 ; i< n ; i++ ){
        int minIndex = i;
        for(int j = i+1 ; j< n ; j++){
            if(arr[minIndex] > arr[j]){
                minIndex = j;
                
            }
        }
        if(minIndex != i){
            // Swap
            int temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
        }
    }
}

// example use
public class Main {
    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};

        selectionSort(arr);

        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}
Selection Sort in Js 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// javascript code
function selectionSort(arr){
    const n = arr.length;
    for(let i = 0 ; i< n ; i++ ){
        let minIndex = i;
        for(let j = i +1 ; j< n ; j++){
            if(arr[minIndex] > arr[j]){
                minIndex = j;
            }
        }
        if(minIndex != i){
            // swap
            let temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
    return arr;
}

// example use
let arr = [10, 7, 8, 9, 1, 5];

selectionSort(arr);

console.log(arr);
Selection Sort in Python 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

# python code
def selectionSort(arr):
    n = len(arr)
    
    for i in range(n):
        minIndex = i
        for j in range(i+1, n):
            if arr[minIndex] > arr[j]:
                minIndex = j;

        if minIndex != i:
            # swap
            arr[j] , arr[j+1] = arr[j+1] , arr[j]

    return arr

# Example use
arr = [10, 7, 8, 9, 1, 5]
selectionSort(arr)
print(arr)

6. Quick Sort

Quick Sort is a divide-and-conquer sorting algorithm that picks a pivot element, partitions the array into elements less than and greater than the pivot and then recursively sorts the partitions. Generally it is unstable.

6.1 Time & Space Complexity:

Time Complexicity
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n²)
Space Complexicity
Best Case: O(log n)

Pros & Cons:

  • Take space due to recursion.
  • Unstable in behavior.
  • Very fast.
  • Cache friendly.

6.2 Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

// 4. Quick Sort with partition code
int partition(int *arr, int low, int high)
{
    int pivot = arr[low];
    int i = low + 1;
    int j = high;

    do
    {
        while (arr[i] <= pivot)
        {
            i++;
        }

        while (arr[j] > pivot)
        {
            j--;
        }

        if (i < j)
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    } while (i < j);

    int value = arr[low];
    arr[low] = arr[j];
    arr[j] = value;

    return j;
}

void QuickSort(int *arr, int low, int high)
{
    if (low < high)
    {
        int partitionIndex = partition(arr, low, high);
        QuickSort(arr, low, partitionIndex - 1);
        QuickSort(arr, partitionIndex + 1, high);
    }
}
Quick Sort in C++ 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include <iostream>
using namespace std;

int partition(int arr[], int low, int high) {
    int pivot = arr[low];
    int i = low + 1;
    int j = high;

    while (true) {
        while (i <= high && arr[i] <= pivot) {
            i++;
        }

        while (arr[j] > pivot) {
            j--;
        }

        if (i < j) {
            swap(arr[i], arr[j]);
        } else {
            break;
        }
    }

    swap(arr[low], arr[j]);
    return j;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int p = partition(arr, low, high);
        quickSort(arr, low, p - 1);
        quickSort(arr, p + 1, high);
    }
}

// example use
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}
Quick Sort in Java 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

// java code
public class QuickSort {

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];
        int i = low + 1;
        int j = high;

        while (true) {
            while (i <= high && arr[i] <= pivot) {
                i++;
            }

            while (arr[j] > pivot) {
                j--;
            }

            if (i < j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            } else {
                break;
            }
        }

        int temp = arr[low];
        arr[low] = arr[j];
        arr[j] = temp;

        return j;
    }

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int p = partition(arr, low, high);
            quickSort(arr, low, p - 1);
            quickSort(arr, p + 1, high);
        }
    }
}

// example use
public class Main {
    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};

        QuickSort.quickSort(arr, 0, arr.length - 1);

        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}
Quick Sort in Js 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

// javascript code
function partition(arr , low , high){
    let pivot = arr[low];
    let i = low + 1;
    let j = high;

    while (true) {
        while (i <= high && arr[i] <= pivot) {
            i++;
        }

        while (arr[j] > pivot) {
            j--;
        }

        if (i < j) {
            let temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        } else {
            break;
        }
    }

    let temp = arr[low];
    arr[low] = arr[j];
    arr[j] = temp;

    return j;
}

function quickSort(arr , low , high){
    if(low < high){
        let partitionIndex = partition(arr , low, high);
        quickSort(arr , low , partitionIndex - 1);
        quickSort(arr , partitionIndex + 1 , high);
    }
}

// example use
let arr = [10, 7, 8, 9, 1, 5];

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

console.log(arr);
Quick Sort in Python 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# python code
def partition(arr, low, high):
    pivot = arr[low]
    i = low + 1
    j = high

    while True:
        while i <= high and arr[i] <= pivot:
            i += 1

        while arr[j] > pivot:
            j -= 1

        if i < j:
            arr[i], arr[j] = arr[j], arr[i]
        else:
            break

    arr[low], arr[j] = arr[j], arr[low]
    return j


def quickSort(arr, low, high):
    if low < high:
        p = partition(arr, low, high)
        quick_sort(arr, low, p - 1)
        quick_sort(arr, p + 1, high)


# Example use
arr = [10, 7, 8, 9, 1, 5]
quickSort(arr, 0, len(arr) - 1)
print(arr)

7. Merge Sort

Merge Sort is a divide-and-conquer algorithm it sorts an array by spliting it into two halves, sorting each half recursively and then merging the sorted halves. it is stable also it is efficient for large datasets. also it recquires extra memory for merging.

7.1 Time & Space Complexity:

Time Complexicity
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)
Space Complexicity
Best Case: O(n)

Pros & Cons:

  • Stable and efficient
  • Requires extra memory

7.2 Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

// 5. Merge Sort
#include <stdio.h>
int arr[] = {12, 6, 47, 65, 38, 24, 98, 75, 82, 13, 44, 37}; // global array Decleration for all the sorting Algorithum



void merge(int *arr, int s, int e){
    int mid = (s+e)/2;      // finding midpoint of the array

    int len1 = mid - s + 1; //length of left part of the array
    int len2 = e - mid;     // length of right part of the array
 
    // dynamic memory allocate
    int *first = new int[len1];     // left array
    int *second = new int[len2];    // right array

    // copy values in left part
    int mainArrayIndex = s;
    for (int i = 0; i < len1; i++)
    {
        first[i] = arr[mainArrayIndex++];
    }

    // copy values in right part
    mainArrayIndex = mid + 1;
    for (int i = 0; i < len2; i++)
    {
        second[i] = arr[mainArrayIndex++];
    }

    //merging 2 sorted arrays
    int index1 = 0;
    int index2 = 0;

    mainArrayIndex = s;

    while (index1 < len1 && index2< len2)
    {
        if (first[index1] < second[index2])
        {
            arr[mainArrayIndex++] = first[index1++];
        }
        else{
            arr[mainArrayIndex++] = second[index2++];
        }
        
    }

    while (index1 < len1)
    {
        arr[mainArrayIndex++] = first[index1++];
    }

    while (index2 < len2)
    {
        arr[mainArrayIndex++] = second[index2++];
    }  
    // free the memory
    delete []first;
    delete []second;
}

void mergesort(int *arr, int s, int e){
    // base case
    if (s >= e)
    {
        return;
    }
    // mid point
    int mid = (s+e)/2;
    // sorting left part
    mergesort(arr , s , mid);
    // sorting right part
    mergesort(arr , mid+1, e);
    // merging sorted arrays
    merge(arr , s, e); 
}


// For Displaying the sorted array or unsorted also
void Display(int *arr, int length)
{
    for (int i = 0; i < length; i++)
    {
        printf("%d ", arr[i]);
    }
}

int main()
{
    // int arr[10]= {1,34,32,25,76,68,45,98,23,44};
    int n=12;
    mergesort(arr , 0 , n-1);
    Display(arr,n);
}
Merge Sort in C++ 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

// cpp code
#include <bits/stdc++.h>
using namespace std;

void merge(int arr[], int s, int e) {
    int mid = s + (e - s) / 2;

    int len1 = mid - s + 1;
    int len2 = e - mid;

    int* first = new int[len1];
    int* second = new int[len2];

    // Copy left part
    int mainArrayIndex = s;
    for (int i = 0; i < len1; i++) {
        first[i] = arr[mainArrayIndex++];
    }

    // Copy right part
    mainArrayIndex = mid + 1;
    for (int i = 0; i < len2; i++) {
        second[i] = arr[mainArrayIndex++];
    }

    // Merge two sorted arrays
    int index1 = 0, index2 = 0;
    mainArrayIndex = s;

    while (index1 < len1 && index2 < len2) {
        if (first[index1] < second[index2]) {
            arr[mainArrayIndex++] = first[index1++];
        } else {
            arr[mainArrayIndex++] = second[index2++];
        }
    }

    while (index1 < len1) {
        arr[mainArrayIndex++] = first[index1++];
    }

    while (index2 < len2) {
        arr[mainArrayIndex++] = second[index2++];
    }

    // Free memory
    delete[] first;
    delete[] second;
}

void mergeSort(int arr[], int s, int e) {
    if (s >= e) {
        return;
    }

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

int main() {
    int arr[] = {12, 6, 47, 65, 38, 24, 98, 75, 82, 13, 44, 37};
    int n = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, n - 1);

    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}
Merge Sort in java 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

// java code
public class MergeSort {

    public static void merge(int[] arr, int s, int e) {
        int mid = s + (e - s) / 2;

        int len1 = mid - s + 1;
        int len2 = e - mid;

        int[] first = new int[len1];
        int[] second = new int[len2];

        // Copy left part
        int mainArrayIndex = s;
        for (int i = 0; i < len1; i++) {
            first[i] = arr[mainArrayIndex++];
        }

        // Copy right part
        mainArrayIndex = mid + 1;
        for (int i = 0; i < len2; i++) {
            second[i] = arr[mainArrayIndex++];
        }

        // Merge two sorted arrays
        int index1 = 0;
        int index2 = 0;
        mainArrayIndex = s;

        while (index1 < len1 && index2 < len2) {
            if (first[index1] < second[index2]) {
                arr[mainArrayIndex++] = first[index1++];
            } else {
                arr[mainArrayIndex++] = second[index2++];
            }
        }

        while (index1 < len1) {
            arr[mainArrayIndex++] = first[index1++];
        }

        while (index2 < len2) {
            arr[mainArrayIndex++] = second[index2++];
        }
    }

    public static void mergeSort(int[] arr, int s, int e) {
        if (s >= e) {
            return;
        }

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

    // Example use
    public static void main(String[] args) {
        int[] arr = {12, 6, 47, 65, 38, 24, 98, 75, 82, 13, 44, 37};
        mergeSort(arr, 0, arr.length - 1);

        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}
Merge Sort in Js 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

// javascript code
function merge(arr, s, e) {
    const mid = Math.floor(s + (e - s) / 2);

    const left = arr.slice(s, mid + 1);
    const right = arr.slice(mid + 1, e + 1);

    let i = 0, j = 0, k = s;

    // Merge the two sorted arrays
    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }

    // Copy remaining elements
    while (i < left.length) {
        arr[k++] = left[i++];
    }

    while (j < right.length) {
        arr[k++] = right[j++];
    }
}

function mergeSort(arr, s, e) {
    if (s >= e) return;

    const mid = Math.floor(s + (e - s) / 2);
    mergeSort(arr, s, mid);
    mergeSort(arr, mid + 1, e);
    merge(arr, s, e);
}

// Example usage
let arr = [12, 6, 47, 65, 38, 24, 98, 75, 82, 13, 44, 37];
mergeSort(arr, 0, arr.length - 1);

console.log(arr);
Merge Sort in python 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

# python code
def merge(arr, s, e):
    mid = s + (e - s) // 2

    # Left and right subarrays
    left = arr[s:mid + 1]
    right = arr[mid + 1:e + 1]

    i = j = 0
    k = s

    # Merge the two sorted halves
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1
        k += 1

    # Copy remaining elements
    while i < len(left):
        arr[k] = left[i]
        i += 1
        k += 1

    while j < len(right):
        arr[k] = right[j]
        j += 1
        k += 1


def merge_sort(arr, s, e):
    if s >= e:
        return

    mid = s + (e - s) // 2
    merge_sort(arr, s, mid)
    merge_sort(arr, mid + 1, e)
    merge(arr, s, e)


# Example usage
arr = [12, 6, 47, 65, 38, 24, 98, 75, 82, 13, 44, 37]
merge_sort(arr, 0, len(arr) - 1)

print(arr)

8. Comparison

Algorithm Best Use Case / Pros Cons / Limitations
Bubble Sort Simple, easy to implement, works for small or nearly sorted arrays Very slow for large arrays, O(n²) time
Insertion Sort Efficient for small or nearly sorted arrays O(n²) time for large arrays
Selection Sort Simple, small datasets, in-place Always O(n²), inefficient for large arrays, unstable
Merge Sort Large datasets, stable sort, predictable O(n log n) time Uses extra memory O(n)
Quick Sort Very fast on average, in-place O(log n) space, good cache performance Worst case O(n²), unstable, pivot choice matters

Which Sorting algo should we use:

  • Small and nearly sorted data: Insertion sort
  • Large datasets: Merge Sort/ Quick sort
  • Memory COnstraints: Heap Sort
  • Integer Data with small range: Counting Sort
  • General Purpose: Quick Sort

Thanks for reading…Don’t forget to leave a comment. 👇

Updated on 10-02-2024
 C, C++
Back | Home