Merge sort The merge sort technique is based on divide and conquers technique. We divide the whole dataset into smaller parts and merge them into a larger piece in sorted order. It is also very effective for worst cases because this algorithm has lower time complexity for the worst case also
Example :
Algorithm Mergesort [A (0..n-1)]
//This algorithm sorts array A [0...n-1] by recursive mergesort.
// Input : An array A(0,n-1) of orderable elements.
// Output : Array A [0,n-1] sorted in non- decreasing order .
{
if n>1
{
Copy A [0…[n/2]-1] to B [0…[n/2]-1]
Copy A [[n/2]… n-1] to C [0…[ n/2] - 1]
MergeSort (B [0…[n/2]-1])
MergeSort (C [0…[ n/2] - 1]) Merge (B, C, A)
}
}
Algorithm: Merge (B [0…p-1], C [0...q-1], A [0...p+q-1])
//Merges two sorted arrays into one sorted array.
//Input: Arrays B [0…p-1] and C [0...q-1] both sorted.
//Output: Sorted array A [0...p+q-1] of the elements of B and C.
{
i ← 0; j←0; k←0
while i<= C[j] A[k] ← B[i];
i← i+1
else A[k] ← C[j]; j← j+1 k ← k+1
}
if i=p
{
copy C [j…q-1] to A[k…p+q-1]
else copy B [i…p-1] to A[k…p+q-1]
}
#include < stdio.h>
/* Function to merge the subarrays of a[] */
void merge(int a[], int beg, int mid, int end)
{
int i, j, k;
int n1 = mid - beg + 1;
int n2 = end - mid;
int LeftArray[n1], RightArray[n2]; //temporary arrays
/* copy data to temp arrays */
for (int i = 0; i < n1; i++)
LeftArray[i] = a[beg + i];
for (int j = 0; j < n2; j++)
RightArray[j] = a[mid + 1 + j];
i = 0; /* initial index of first sub-array */
j = 0; /* initial index of second sub-array */
k = beg; /* initial index of merged sub-array */
while (i < n1 && j < n2)
{
if(LeftArray[i] <= RightArray[j])
{
a[k] = LeftArray[i];
i++;
}
else
{
a[k] = RightArray[j];
j++;
}
k++;
}
while (i< n1)
{
a[k] = LeftArray[i];
i++;
k++;
}
while (j < n2)
{
a[k] = RightArray[j];
j++;
k++;
}
}
void mergeSort(int a[], int beg, int end)
{
if (beg < end)
{
int mid = (beg + end) / 2;
mergeSort(a, beg, mid);
mergeSort(a, mid + 1, end);
merge(a, beg, mid, end);
}
}
/* Function to print the array */
void printArray(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\n");
}
int main()
{
int a[] = { 12, 31, 25, 8, 32, 17, 40, 42 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArray(a, n);
mergeSort(a, 0, n - 1);
printf("After sorting array elements are - \n");
printArray(a, n);
return 0;
}
Code
class Merge {
/* Function to merge the subarrays of a[] */
void merge(int a[], int beg, int mid, int end)
{
int i, j, k;
int n1 = mid - beg + 1;
int n2 = end - mid;
/* temporary Arrays */
int LeftArray[] = new int[n1];
int RightArray[] = new int[n2];
/* copy data to temp arrays */
for (i = 0; i < n1; i++)
LeftArray[i] = a[beg + i];
for (j = 0; j < n2; j++)
RightArray[j] = a[mid + 1 + j];
i = 0; /* initial index of first sub-array */
j = 0; /* initial index of second sub-array */
k = beg; /* initial index of merged sub-array */
while (i < n1 && j < n2)
{
if(LeftArray[i] <= RightArray[j])
{
a[k] = LeftArray[i];
i++;
}
else
{
a[k] = RightArray[j];
j++;
}
k++;
}
while (i< n1)
{
a[k] = LeftArray[i];
i++;
k++;
}
while (j< n2)
{
a[k] = RightArray[j];
j++;
k++;
}
}
void mergeSort(int a[], int beg, int end)
{
if (beg < end)
{
int mid = (beg + end) / 2;
mergeSort(a, beg, mid);
mergeSort(a, mid + 1, end);
merge(a, beg, mid, end);
}
}
/* Function to print the array */
void printArray(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
System.out.print(a[i] + " ");
}
public static void main(String args[])
{
int a[] = { 11, 30, 24, 7, 31, 16, 39, 41 };
int n = a.length;
Merge m1 = new Merge();
System.out.println("\nBefore sorting array elements are - ");
m1.printArray(a, n);
m1.mergeSort(a, 0, n - 1);
System.out.println("\nAfter sorting array elements are - ");
m1.printArray(a, n);
System.out.println("");
}
}
Code
# Merges two subarrays of arr[].
# First subarray is arr[l..m]
# Second subarray is arr[m+1..r]
def merge_sort(unsortedList):
if len(unsortedList) > 1:
mid = len(unsortedList) // 2
leftList = unsortedList[:mid]
rightList = unsortedList[mid:]
# Recursive call when we go two list (left and right) for sorting
merge_sort(leftList)
merge_sort(rightList)
# Because we have two lists, so we need to iterators for iteration of each list
m = 0
n = 0
# We need one common iterator which iterates to the main list
z = 0
while m < len(leftList) and n < len(rightList):
if leftList[m] <= rightList[n]:
# Here we are using the first left side elements
unsortedList[z] = leftList[m]
# Increment the main iterator
m += 1
else:
unsortedList[z] = rightList[n]
n += 1
z += 1
# If values are left in the list, then we process here
while m < len(leftList):
unsortedList[z] = leftList[m]
m += 1
z += 1
while n < len(rightList):
unsortedList[z]=rightList[n]
n += 1
z += 1
unsortedList = [23,56,0,23,85,100,200,12,32,78,90,102]
merge_sort(unsortedList)
print(unsortedList)
Code
22 33 11 88 33 44
11 22 33 33 44 88
Insertion sort
Radix sort