Example 1: merge sort c#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Merge_sort
{
class Program
{
static void Main(string[] args)
{
List<int> unsorted = new List<int>();
List<int> sorted;
Random random = new Random();
Console.WriteLine("Original array elements:" );
for(int i = 0; i< 10;i++){
unsorted.Add(random.Next(0,100));
Console.Write(unsorted[i]+" ");
}
Console.WriteLine();
sorted = MergeSort(unsorted);
Console.WriteLine("Sorted array elements: ");
foreach (int x in sorted)
{
Console.Write(x+" ");
}
Console.Write("\n");
}
private static List<int> MergeSort(List<int> unsorted)
{
if (unsorted.Count <= 1)
return unsorted;
List<int> left = new List<int>();
List<int> right = new List<int>();
int middle = unsorted.Count / 2;
for (int i = 0; i < middle;i++)
{
left.Add(unsorted[i]);
}
for (int i = middle; i < unsorted.Count; i++)
{
right.Add(unsorted[i]);
}
left = MergeSort(left);
right = MergeSort(right);
return Merge(left, right);
}
private static List<int> Merge(List<int> left, List<int> right)
{
List<int> result = new List<int>();
while(left.Count > 0 || right.Count>0)
{
if (left.Count > 0 && right.Count > 0)
{
if (left.First() <= right.First())
{
result.Add(left.First());
left.Remove(left.First());
}
else
{
result.Add(right.First());
right.Remove(right.First());
}
}
else if(left.Count>0)
{
result.Add(left.First());
left.Remove(left.First());
}
else if (right.Count > 0)
{
result.Add(right.First());
right.Remove(right.First());
}
}
return result;
}
}
}
Example 2: merge sort in python
def mergeSort(myList):
if len(myList) > 1:
mid = len(myList)
left = myList[:mid]
right = myList[mid:]
# Recursive call on each half
mergeSort(left)
mergeSort(right)
# Two iterators for traversing the two halves
i = 0
j = 0
# Iterator for the main list
k = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
# The value from the left half has been used
myList[k] = left[i]
# Move the iterator forward
i += 1
else:
myList[k] = right[j]
j += 1
# Move to the next slot
k += 1
# For all the remaining values
while i < len(left):
myList[k] = left[i]
i += 1
k += 1
while j < len(right):
myList[k]=right[j]
j += 1
k += 1
myList = [54,26,93,17,77,31,44,55,20]
mergeSort(myList)
print(myList)
Example 3: merge sort
#include <iostream>
using namespace std;
void merge(int arr[],int start,int mid,int end)
{
int n1=mid-start+1;
int n2=end-mid;
int l[n1],m[n2];
for(int i=0;i<n1;i++)
{
l[i]=arr[start+i];
}
for(int j=0;j<n2;j++)
{
m[j]=arr[mid+1+j];
}
int i=0;
int j=0;
int k=start;
while(i<n1&&j<n2)
{
if(l[i]<m[j])
{
arr[k]=l[i];
k++;
i++;
}
else
{
arr[k]=m[j];
k++;
j++;
}
}
while(i<n1)
{
arr[k]=l[i];
k++;
i++;
}
while(j<n2)
{
arr[k]=m[j];
k++;
j++;
}
}
void mergesort(int arr[],int start,int end)
{
if(start<end)
{
int mid=(start+end)/2;
mergesort(arr,start,mid);
mergesort(arr,mid+1,end);
merge(arr,start,mid,end);
}
}
void display(int arr[],int n)
{
for(int i=0;i<n;i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
}
int main()
{
int n;
cout<<"enter the size of the array:"<<endl;
cin>>n;
cout<<"enter the elements of the array:"<<endl;
int arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
cout<<"array as it is:"<<endl;
display(arr,n);
cout<<"sorted array:"<<endl;
mergesort(arr,0,n-1);
display(arr,n);
return 0;
}
Example 4: Merge sort java
public class JavaMergeSort
{
void sorting(int[] num, int left, int main, int right)
{
int list1 = main - left + 1;
int list2 = right - main;
int[] L = new int[list1];
int[] R = new int[list2];
for(int a = 0; a < list1; ++a)
L[a] = num[left + a];
for(int b = 0; b < list2; ++b)
R[b] = num[main + 1+ b];
int p = 0, q = 0;
int r = left;
while(p < list1 && q < list2)
{
if(L[p] <= R[q])
{
num[r] = L[p];
p++;
}
else
{
num[r] = R[q];
q++;
}
r++;
}
while(p < list1)
{
num[r] = L[p];
p++;
r++;
}
while(q < list2)
{
num[r] = R[q];
q++;
r++;
}
}
void sort(int[] arrNum, int l, int r)
{
if(l < r)
{
int m = (l + r) / 2;
sort(arrNum, l, m);
sort(arrNum , m+1, r);
sorting(arrNum, l, m, r);
}
}
static void displayArray(int[] arr)
{
int number = arr.length;
for(int a = 0; a < number; ++a)
System.out.print(arr[a] + " ");
System.out.println();
}
public static void main(String[] args)
{
int[] arrNumbers = {33, 00, 55, 11, 22, 44};
System.out.println("Before sorting - ");
displayArray(arrNumbers);
JavaMergeSort obj = new JavaMergeSort();
obj.sort(arrNumbers, 0, arrNumbers.length - 1);
System.out.println("\nAfter sorting - ");
displayArray(arrNumbers);
}
}
Example 5: merge sort
function merge(list, start, midpoint, end) {
const left = list.slice(start, midpoint);
const right = list.slice(midpoint, end);
for (let topLeft = 0, topRight = 0, i = start; i < end; i += 1) {
if (topLeft >= left.length) {
list[i] = right[topRight++];
} else if (topRight >= right.length) {
list[i] = left[topLeft++];
} else if (left[topLeft] < right[topRight]) {
list[i] = left[topLeft++];
} else {
list[i] = right[topRight++];
}
}
}
function mergesort(list, start = 0, end = undefined) {
if (end === undefined) {
end = list.length;
}
if (end - start > 1) {
const midpoint = ((end + start) / 2) >> 0;
mergesort(list, start, midpoint);
mergesort(list, midpoint, end);
merge(list, start, midpoint, end);
}
return list;
}
mergesort([4, 7, 2, 6, 4, 1, 8, 3]);
Example 6: merge sort
# Python3 recursive merge sort algorithm -> O(n*log(n))
def merge_sort(A):
def merge(l, r):
i = j = 0
n = [] # merging container
while i < len(l) or j < len(r):
# if no more elements to the right,
# add remaining left elements
if i == len(l):
n.extend(r[j:])
break
# if no more elements to the left,
# add remaining right elements
if j == len(r):
n.extend(l[i:])
break
# if elements left on both sides,
# add smaller element
a, b = l[i], r[j]
if a < b:
n.append(a)
i += 1
else:
n.append(b)
j += 1
return n
# divide list down to single-elements
s = len(A)
if s > 1:
s
l = merge_sort(A[:s]) # split left
r = merge_sort(A[s:]) # split right
return merge(l, r) # merge sides in order
else:
return A