JAVASCRIPT

mergesort

"""Mergesort
	The cleaner version than geeks4geeks. Although check that code out too!
"""
## Method 1: Two functions
def mergesort(lst):
    # Is sortable
    if len(lst) > 1:
        # Get mid-point
        mid = len(lst) // 2
        
        # Recursive Partition
        left = mergesort(lst[:mid])
        right = mergesort(lst[mid:])
        
        # Merging
        return merge(left, right)
    return lst

def merge(left, right):
    new = []
    
    # Left and right not empty
    while left and right:
        # Compare 1st elements of left and right, sort accordingly
        if left[0] < right[0]:
            new.append(left.pop(0))
        else:
            new.append(right.pop(0))
    
    # Append the leftover nums
    return new + left + right

## Method 2: Nested functions
def merge(nums):
    # Recursive partition
    if len(nums) > 1:
        # Midpoint
        mid = len(nums) // 2
        
        left = merge(nums[:mid])
        right = merge(nums[mid:])
        
        # Sorting
        def go(left, right):
            newlist = []
            
            # Sort by comparing 1st elements of both lists
            while left and right:
                if left[0] < right[0]:
                    newlist.append(left.pop(0))
                else:
                    newlist.append(right.pop(0))
                    
            # Cleanup unsorted elements            
            return newlist + left + right
        return go(left, right)
    return nums

mergesort

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        int size = 5 ;
      double[] arrayList = new double[size];
      for(int i = 0 ; i < arrayList.length ; ++i){
          arrayList[i] = (Math.random()*1000);
      }

        mergeSort(arrayList,0,arrayList.length-1);
        print(arrayList);

    }
    public static void print(double []  arrayList){
        for(int i = 0 ; i < arrayList.length; ++i){
            System.out.println(arrayList[i]);
        }
    }
    public  static void mergeSort(double [] arr , int l , int r){
        if(l<r){
            int m = l+(r-l)/2;

            mergeSort(arr,l,m);
            mergeSort(arr,m+1,r);

            merge(arr,l , m , r);
        }

    }

    public  static void merge(double[] unsorted, int l , int m , int r){
        int i ,j ,k;
        int arr1 = m - l +1;
        int arr2 = r - m ;
        double [] left = new double[arr1];
        double [] right = new double[arr2];
        for(int f = 0 ; f < arr1 ; ++f){
            left[f] = unsorted[l+f];
        }
        for (int s = 0 ; s < arr2 ; ++s){
           right[s] = unsorted[m+1+s];
        }

        i = j = 0;
        k = l ;

        while(i < arr1 && j < arr2){
            if(left[i] <= right[j]){
                unsorted[k] = left[i];
                ++i;
            }
            else {
                unsorted[k]= right[j];
                ++j;
            }
            ++k;
        }

        while(i<arr1){
            unsorted[k] = left[i];
            ++i;++k;
        }
        while(j<arr2){
            unsorted[k] = right[j];
            ++j;++k;
        }


    }
}

mergeSort

# MergeSort in Python


def mergeSort(array):
    if len(array) > 1:

        #  r is the point where the array is divided into two subarrays
        r = len(array)//2
        L = array[:r]
        M = array[r:]

        # Sort the two halves
        mergeSort(L)
        mergeSort(M)

        i = j = k = 0

        # Until we reach either end of either L or M, pick larger among
        # elements L and M and place them in the correct position at A[p..r]
        while i < len(L) and j < len(M):
            if L[i] < M[j]:
                array[k] = L[i]
                i += 1
            else:
                array[k] = M[j]
                j += 1
            k += 1

        # When we run out of elements in either L or M,
        # pick up the remaining elements and put in A[p..r]
        while i < len(L):
            array[k] = L[i]
            i += 1
            k += 1

        while j < len(M):
            array[k] = M[j]
            j += 1
            k += 1


# Print the array
def printList(array):
    for i in range(len(array)):
        print(array[i], end=" ")
    print()


# Driver program
if __name__ == '__main__':
    array = [6, 5, 12, 10, 9, 1]

    mergeSort(array)

    print("Sorted array is: ")
    printList(array)

mergesort

function merge(left, right) {
    let arr = []
    // Break out of loop if any one of the array gets empty
    while (left.length && right.length) {
        // Pick the smaller among the smallest element of left and right sub arrays 
        if (left[0] < right[0]) {
            arr.push(left.shift())  
        } else {
            arr.push(right.shift()) 
        }
    }
    
    // Concatenating the leftover elements
    // (in case we didn't go through the entire left or right array)
    return [ ...arr, ...left, ...right ]
}

merge sort function

def merge_sort(arr):
    """Execute the merge sort algorithm"""
    if len(arr) > 1:
        # recursive case
        mid = len(arr) // 2 # find the midpoint of the array
        l = arr[:mid] # define the left half of the array
        r = arr[mid:] # define the right half of the array

        l = merge_sort(l) # sort the left half by calling this function
        r = merge_sort(r) # sort the right half by calling this function

        # now merge the two lists
        merged = [] # define an empty merged array
        while len(l) > 0 and len(r) > 0:
            # compare the heads of the left and right array
            if l[0] <= r[0]:
                # if the head of the left list is smaller than the head of the right list
                # pop the head of the left list and append it to the merged list
                merged.append(l.pop(0))
            else:
                # otherwise, pop the head of the right list and append that
                merged.append(r.pop(0))

        # add any elements remaining in the left or right list to the merged list
        merged = merged + l + r

        return merged
    else:
        # base case
        return arr

sorting merge

# Merge Sorting:

def merge(a,b):
    merged_list = []
    len_a,len_b = len(a),len(b)
    index_a,index_b = 0,0

    while index_a < len_a and index_b < len_b:
        if a[index_a] < b[index_b]:
            merged_list.append(a[index_a])
            index_a += 1
        else:
            merged_list.append(b[index_b])
            index_b += 1

    if index_a < len_a:
        merged_list.extend(a[index_a:])
    elif index_b < len_b:
        merged_list.extend(b[index_b:])
    return merged_list

# Now merge sorting:
def merge_sort(L):
    if len(L) <= 1:
        return L
    mid = len(L)//2
    left = merge_sort(L[:mid])
    right = merge_sort(L[mid:])
    return merge(left,right)

# input list:
L = [[4,7,2,3],[10],[10,9,8,7,6],[2,3,1],[1,2],[2,1]]
total_sorted_list = []
for i in L:
    sorted_list = merge_sort(i)
    print("Original List:",i)
    print("Sorted List:",sorted_list)
    print()

# Output:
Original List: [4, 7, 2, 3]
Sorted List: [2, 3, 4, 7]

Original List: [10]
Sorted List: [10]

Original List: [10, 9, 8, 7, 6]
Sorted List: [6, 7, 8, 9, 10]

Original List: [2, 3, 1]
Sorted List: [1, 2, 3]

Original List: [1, 2]
Sorted List: [1, 2]

Original List: [2, 1]
Sorted List: [1, 2]

manual merge sort

# Python program for implementation of MergeSort
def mergeSort(arr):
    if len(arr) > 1:
 
         # Finding the mid of the array
        mid = len(arr)//2
 
        # Dividing the array elements
        L = arr[:mid]
 
        # into 2 halves
        R = arr[mid:]
 
        # Sorting the first half
        mergeSort(L)
 
        # Sorting the second half
        mergeSort(R)
 
        i = j = k = 0
 
        # Copy data to temp arrays L[] and R[]
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1
 
        # Checking if any element was left
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1
 
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
 
# Code to print the list
 
 
def printList(arr):
    for i in range(len(arr)):
        print(arr[i], end=" ")
    print()
 
 
# Driver Code
if __name__ == '__main__':
    arr = [12, 11, 13, 5, 6, 7]
    print("Given array is", end="
")
    printList(arr)
    mergeSort(arr)
    print("Sorted array is: ", end="
")
    printList(arr)
 
# This code is contributed by Mayank Khanna

mergeSort

export function mergeSort (arr){
  if(arr.length <= 1){
    return arr;
  }
  let mid = Math.floor(arr.length /2);
  return merge(
    mergeSort (arr.slice(0,mid)),
    mergeSort (arr.slice(mid))
  )
}

function merge(left,right) {
  let mergeArr = [];
  let i = 0,j = 0;

  while(i < left.length && j < right.length) {
    if(left[i] < right[j]){
      mergeArr.push(left[i++])
    
    }else {
      mergeArr.push(right[j++])
    }
  }
  return mergeArr.concat(left.slice(i)).concat(right.slice(j));
}