Merge Sort Algorithm

Merge sort Algorithm

Merge sort is a type of sorting algorithm that uses a divideandconquer approach to sort an array of items. It works by breaking the array down into smaller subarrays and then merging them back together in a specific order to produce a sorted array.

The process of breaking the array down into subarrays is repeated until each subarray consists of a single element, which is the base case for the algorithm.

The merge step then combines the subarrays together in a specific order to produce the sorted array. In essence, merge sort is a combination of two techniques: divide and conquer, and merging.

Merge sort is an efficient, general-purpose, comparison-based sorting algorithm. It works by dividing an array into two halves, sorting each half, and then merging the sorted halves back together.

pseudocode

function mergeSort(array)
    if length of array <= 1
        return array
    else
        middle = length of array / 2
        left = first half of array
        right = second half of array
        left = mergeSort(left)
        right = mergeSort(right)
        return merge(left, right)

function merge(left, right)
    result = empty array
    while left and right are both non-empty
        if first element of left is less than or equal to first element of right
            append first element of left to result
            remove first element of left
        else
            append first element of right to result
            remove first element of right
    while left is non-empty
        append first element of left to result
        remove first element of left
    while right is non-empty
        append first element of right to result
        remove first element of right
    return result

Merge Sort Step by step Explanation

1. Divide the input array into two halves.

We will use the divide-and-conquer approach to divide the array into two halves. This means we will use a recursive approach to divide the array into two halves until it is broken down into individual elements.

2. Recursively sort each half.

We will use the same approach to recursively sort each half of the array. This means we will apply the same divide-and-conquer approach to each half until the array is broken down into individual elements.

3. Merge the sorted halves into one sorted array.

We will use the merge procedure to combine the two sorted halves into one sorted array. The merging step will involve comparing the elements of each half, and then adding them to the sorted array in the correct order.

4. Return the sorted array.

Finally, we will return the sorted array. This will be the final, sorted array that we have created.

The time complexity of merge sort is O(n*log(n)), making it more efficient than many other sorting algorithms, such as bubble sort and insertion sort. It is also a stable sort, meaning that the order of elements that compare as equal will be preserved.

Merge Sort Code in Multiple Language

C++

#include <iostream>
#include <vector>

using namespace std;

void merge(vector<int>& array, vector<int>& left, vector<int>& right) {
    int i = 0, j = 0, k = 0;
    while (i < left.size() && j < right.size()) {
        if (left[i] <= right[j]) {
            array[k] = left[i];
            i++;
        } else {
            array[k] = right[j];
            j++;
        }
        k++;
    }
    while (i < left.size()) {
        array[k] = left[i];
        i++;
        k++;
    }
    while (j < right.size()) {
        array[k] = right[j];
        j++;
        k++;
    }
}

void mergeSort(vector<int>& array) {
    if (array.size() <= 1) {
        return;
    }
    int middle = array.size() / 2;
    vector<int> left(array.begin(), array.begin() + middle);
    vector<int> right(array.begin() + middle, array.end());
    mergeSort(left);
    mergeSort(right);
    merge(array, left, right);
}

int main() {
    vector<int> array = {4, 2, 6, 1, 3, 5};
    mergeSort(array);
    for (int i : array) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}

Python

def merge(left, right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left[0])
            left.pop(0)
        else:
            result.append(right[0])
            right.pop(0)
    while left:
        result.append(left[0])
        left.pop(0)
    while right:
        result.append(right[0])
        right.pop(0)
    return result

def merge_sort(array):
    if len(array) <= 1:
        return array
    middle = len(array) // 2
    left = array[:middle]
    right = array[middle:]
    left = merge_sort(left)
    right = merge_sort(right)
    return merge(left, right)

array = [4, 2, 6, 1, 3, 5]
sorted_array = merge_sort(array)
print(sorted_array)

 

JavaScript

function merge(left, right) {
    let result = [];
    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    while (left.length) {
        result.push(left.shift());
    }
    while (right.length) {
        result.push(right.shift());
    }
    return result;
}

function mergeSort(array) {
    if (array.length <= 1) {
        return array;
    }
    let middle = Math.floor(array.length / 2);
    let left = array.slice(0, middle);
    let right = array.slice(middle);
    left = mergeSort(left);
    right = mergeSort(right);
    return merge(left, right);
}

let array = [4, 2, 6, 1, 3, 5];
let sortedArray = mergeSort(array);
console.log(sortedArray);

PHP

<?php

function merge($left, $right) {
    $result = [];
    while (count($left) && count($right)) {
        if ($left[0] <= $right[0]) {
            $result[] = array_shift($left);
        } else {
            $result[] = array_shift($right);
        }
    }
    while (count($left)) {
        $result[] = array_shift($left);
    }
    while (count($right)) {
        $result[] = array_shift($right);
    }
    return $result;
}

function mergeSort($array) {
    if (count($array) <= 1) {
        return $array;
    }
    $middle = count($array) / 2;
    $left = array_slice($array, 0, $middle);
    $right = array_slice($array, $middle);
    $left = mergeSort($left);
    $right = mergeSort($right);
    return merge($left, $right);
}

$array = [4, 2, 6, 1, 3, 5];
$sortedArray = mergeSort($array);
print_r($sortedArray);

Java

import java.util.Arrays;

public class MergeSort {

    public static void merge(int[] array, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                array[k] = left[i];
                i++;
            } else {
                array[k] = right[j];
                j++;
            }
            k++;
        }
        while (i < left.length) {
            array[k] = left[i];
            i++;
            k++;
        }
        while (j < right.length) {
            array[k] = right[j];
            j++;
            k++;
        }
    }

    public static void mergeSort(int[] array) {
        if (array.length <= 1) {
            return;
        }
        int middle = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, middle);
        int[] right = Arrays.copyOfRange(array, middle, array.length);
        mergeSort(left);
        mergeSort(right);
        merge(array, left, right);
    }

    public static void main(String[] args) {
        int[] array = {4, 2, 6, 1, 3, 5};
        mergeSort(array);
        System.out.println(Arrays.toString(array));
    }
}

List of Sorting Algorithms

Bubble Sort Algorithm

Selection sort Algorithm

Insertion sort: a Sorting Algorithm

Message Hi Message: Jokes

 

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.