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 in c++
using namespace std;
void merge(int arr[], int l, int m, int r)
{
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
int i = 0;
int j = 0;
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[],int l,int r){
if(l>=r){
return;
}
int m = (l+r-1)/2;
mergeSort(arr,l,m);
mergeSort(arr,m+1,r);
merge(arr,l,m,r);
}
void printArray(int A[], int size)
{
for (int i = 0; i < size; i++)
cout << A[i] << " ";
}
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
cout << "Given array is \n";
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
cout << "\nSorted array is \n";
printArray(arr, arr_size);
return 0;
}
Example 3: 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 4: merge sort algo
def mergeSort(arr):
if len(arr) >1:
mid = len(arr)//2
L = arr[:mid]
R = arr[mid:]
mergeSort(L)
mergeSort(R)
i = j = k = 0
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
while i < len(L):
arr[k] = L[i]
i+= 1
k+= 1
while j < len(R):
arr[k] = R[j]
j+= 1
k+= 1
def printList(arr):
for i in range(len(arr)):
print(arr[i], end =" ")
print()
if __name__ == '__main__':
arr = [12, 11, 13, 5, 6, 7]
print ("Given array is", end ="\n")
printList(arr)
mergeSort(arr)
print("Sorted array is: ", end ="\n")
printList(arr)
Example 5: merge sort algorithm
/*
a[] is the array, p is starting index, that is 0,
and r is the last index of array.
*/
// lets take a[5] = {32, 45, 67, 2, 7} as the array to be sorted.
// merge sort function
void mergeSort(int a[], int p, int r)
{
int q;
if(p < r)
{
q = (p + r) / 2;
mergeSort(a, p, q);
mergeSort(a, q+1, r);
merge(a, p, q, r);
}
}
// function to merge the subarrays
void merge(int a[], int p, int q, int r)
{
int b[5]; //same size of a[]
int i, j, k;
k = 0;
i = p;
j = q + 1;
while(i <= q && j <= r)
{
if(a[i] < a[j])
{
b[k++] = a[i++]; // same as b[k]=a[i]; k++; i++;
}
else
{
b[k++] = a[j++];
}
}
while(i <= q)
{
b[k++] = a[i++];
}
while(j <= r)
{
b[k++] = a[j++];
}
for(i=r; i >= p; i--)
{
a[i] = b[--k]; // copying back the sorted list to a[]
}
}
// function to print the array
void printArray(int a[], int size)
{
int i;
for (i=0; i < size; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
int main()
{
int arr[] = {32, 45, 67, 2, 7};
int len = sizeof(arr)/sizeof(arr[0]);
printf("Given array: \n");
printArray(arr, len);
// calling merge sort
mergeSort(arr, 0, len - 1);
printf("\nSorted array: \n");
printArray(arr, len);
return 0;
}
Example 6: merge sort c++
/* >>>>>>>> (Recursive function that sorts a sequence of) <<<<<<<<<<<<
>>>>>>>> (numbers in ascending order using the merge function) <<<< */
std::vector<int> sort(size_t start, size_t length, const std::vector<int>& vec)
{
if(vec.size()==0 ||vec.size() == 1)
return vec;
vector<int> left,right; //===> creating left and right vectors
size_t mid_point = vec.size()/2; //===> midle point between the left vector and the right vector
for(int i = 0 ; i < mid_point; ++i){left.emplace_back(vec[i]);} //===> left vector
for(int j = mid_point; j < length; ++j){ right.emplace_back(vec[j]);} //===> right vector
left = sort(start,mid_point,left); //===> sorting the left vector
right = sort(mid_point,length-mid_point,right);//===> sorting the right vector
return merge(left,right); //===> all the function merge to merge between the left and the right
}
/*
>>>>> (function that merges two sorted vectors of numberss) <<<<<<<<< */
vector<int> merge(const vector<int>& a, const vector<int>& b)
{
vector<int> merged_a_b(a.size()+b.size(),0); // temp vector that includes both left and right vectors
int i = 0;
int j = 0;
int k = 0;
int left_size = a.size();
int right_size = b.size();
while(i<left_size && j<right_size)
{
if(a[i]<b[j])
{
merged_a_b[k]=a[i];
i++;
}
else
{
merged_a_b[k]=b[j];
j++;
}
k++;
}
while(i<left_size)
{
merged_a_b[k]=a[i];
i++;
k++;
}
while(j<right_size)
{
merged_a_b[k]=b[j];
j++;
k++;
}
return merged_a_b;
}