Informal explanation of merge in merge sort
We have two arrays that are already sorted: one on the left and the other on the right
We stick them together (left+right array).
We then compare the terms starting from the 0th([0] term for both left and right arrays.
So left[0] compare with right[0](or more correctly, array[0] with array[mid+1])
We create a blank array
If the left[0] term is bigger, we add left[0] to blank array as its first term.
If the right[0] term is bigger, we add right[0] to the blank array as its first term.
Assuming left[0] is bigger, We then move to left[1] vs right[0].
We keep doing this until we run out of terms in one of the arrays.
We then stick the remaining terms of the array where we didn't run out to the end of our (originally, now no longer) blank array.
The blank array has now been sorted!
"""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
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 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)
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 ]
}