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++) //Dividing the unsorted list
{
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()) //Comparing First two elements to see which is smaller
{
result.Add(left.First());
left.Remove(left.First()); //Rest of the list minus the first element
}
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
//merge sort
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 3: Merge sort
class Sort
{
void merge(int arr[], int left, int middle, int right)
{
int low = middle - left + 1; //size of the left subarray
int high = right - middle; //size of the right subarray
int L[] = new int[low]; //create the left and right subarray
int R[] = new int[high];
int i = 0, j = 0;
for (i = 0; i < low; i++) //copy elements into left subarray
{
L[i] = arr[left + i];
}
for (j = 0; j < high; j++) //copy elements into right subarray
{
R[j] = arr[middle + 1 + j];
}
int k = left; //get starting index for sort
i = 0; //reset loop variables before performing merge
j = 0;
while (i < low && j < high) //merge the left and right subarrays
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < low) //merge the remaining elements from the left subarray
{
arr[k] = L[i];
i++;
k++;
}
while (j < high) //merge the remaining elements from right subarray
{
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int left, int right) //helper function that creates the sub cases for sorting
{
int middle;
if (left < right) { //sort only if the left index is lesser than the right index (meaning that sorting is done)
middle = (left + right) / 2;
mergeSort(arr, left, middle); //left subarray
mergeSort(arr, middle + 1, right); //right subarray
merge(arr, left, middle, right); //merge the two subarrays
}
}
void display(int arr[]) //display the array
{
for (int i=0; i<arr.length; ++i)
{
System.out.print(arr[i]+" ");
}
}
public static void main(String args[])
{
int arr[] = { 9, 3, 1, 5, 13, 12 };
Sort ob = new Sort();
ob.mergeSort(arr, 0, arr.length - 1);
ob.display(arr);
}
}
Example 4: mergesort
def merge_sort(arr):
if len(arr) > 1:
middle = len(arr) // 2
left = arr[:middle]
right = arr[middle:]
merge_sort(left)
merge_sort(right)
i = len(arr) - 1
while i >= 0:
if left and right:
if left[-1] >= right[-1]:
arr[i] = left.pop()
else:
arr[i] = right.pop()
else:
arr[i] = left.pop() if left else right.pop()
i -= 1
return arr
Example 5: merge sort
// @see https://www.youtube.com/watch?v=es2T6KY45cA&vl=en
// @see https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
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
def merge_sort(A):
def merge(l, r):
i = j = 0
n = []
while i < len(l) or j < len(r):
if i == len(l):
n.extend(r[j:])
break
if j == len(r):
n.extend(l[i:])
break
a, b = l[i], r[j]
if a < b:
n.append(a)
i += 1
else:
n.append(b)
j += 1
return n
s = len(A)
if s > 1:
s //= 2
l = merge_sort(A[:s])
r = merge_sort(A[s:])
return merge(l, r)
else:
return A