MergeSort Algorithm in Java

Mergesort algorithm is a divide and conquer algorithm. Its not efficient as Quicksort algorithm but in some cases Mergesort is better than Quicksort. For example its a linked list then Quicksort is costly since in a linkedlist accessing random elements is costly , since in Quicksort elements to be accessed randomly.

Asymptotic Complexity
Something	Time Complexity	Space Complexity
Worst Case Performance	O (n log n)
Best Case Performance	O (n log n)
Average Case Performance	O(n log n)
Worst Case space Complexity		O (n)

	import java.io.*;
	import java.util.*;
	public class MergeSortAlgo{
	static int arr[] = { 11,34,55,67,23,64,78,34,12,84,33,5,5};
	private void MergeSort(int [] arr)
	{
	System.out.println("Split array " + Arrays.toString(arr));
	if(arr.length > 1)
	{
	int [] leftpart;
	int [] rightpart;
	int mid = arr.length / 2;
	if(arr.length%2 == 0)
	{
	leftpart = new int[mid];
	rightpart = new int[mid];
	System.arraycopy(arr, 0, leftpart, 0, mid);
	System.arraycopy(arr, mid, rightpart, 0, mid);
	}
	else
	{
	leftpart = new int[mid+1];
	rightpart = new int[mid];
	System.arraycopy(arr, 0, leftpart, 0, mid+1);
	System.arraycopy(arr, mid+1, rightpart, 0, mid);
	}
	MergeSort(leftpart);
	MergeSort(rightpart);
	int i=0,j=0,k=0;
	while ((i<leftpart.length) && (j<rightpart.length))
	{
	if(leftpart[i] < rightpart[j])
	{
	arr[k] = leftpart[i];
	i++;
	}
	else
	{
	arr[k] = rightpart[j];
	j++;
	}
	k++;
	}
	while(i < leftpart.length)
	{
	arr[k] = leftpart[i];
	i++;
	k++;
	}
	while(j < rightpart.length)
	{
	arr[k] = rightpart[j];
	j++;
	k++;
	}
	}
	System.out.println("Mergerd array " + Arrays.toString(arr));
	}
	public static void main(String []args)
	{
	System.out.println("Unsorted array " + Arrays.toString(arr));
	MergeSortAlgo obj = new MergeSortAlgo();
	obj.MergeSort(arr);
	System.out.println("Sorted array " + Arrays.toString(arr));
	}
	}

view raw MergeSortAlgo.java hosted with ❤ by GitHub

Bubblesort algorithm implementation in C

Here is a bubblesort implementation in C. Although bubblesort is not a efficient algorithm, its a simple algorithm to demonstrate what is a sorting algorithm

Asymptotic Complexity
Time Complexity	Space Complexity
n^2	1

If you want to see the same implementation in python please click the following link: Bubblesort implementation in python

	#include <stdio.h>
	#include <string.h>
	#include <stdbool.h>
	void bubblesort(int *arr, int size)
	{
	int i = 0, temp;
	int j = 1;
	bool swapped = true;
	while(swapped)
	{
	swapped = false;
	i = 0;
	for(i; i< size-j; i++)
	{
	if (arr[i] > arr[i+1])
	{
	temp = arr[i];
	arr[i] = arr[i+1];
	arr[i+1] = temp;
	swapped = true;
	}
	}
	j++;
	}
	}
	main()
	{
	int arr[] = { 12,4,6,7,33,43,87,32,7,34,2,8,43,23,7,3};
	int i;
	int size = sizeof(arr)/sizeof(arr[0]);
	for (i=0; i<size; i++)
	printf(" %d",arr[i]);
	bubblesort(arr, size);
	printf("\n");
	for (i=0; i<size; i++)
	printf(" %d",arr[i]);
	}

view raw bubblesort.c hosted with ❤ by GitHub

Bubblesort algorithm in Java

Given below is the Bubblesort algorithm in Java. Although bubblesort is not a efficient algorithm, its a simple algorithm to demonstrate what is a sorting algorithm

Asymptotic Complexity
Time Complexity	Space Complexity
n^2	1

If you want to see the same implementation in python please click the following link: Bubblesort implementation in python

If you would like to see how this implentation would look like in C click the following link: Bubblesort implementation in C

	public class BBSort
	{
	private void bubblesort(int [] arr)
	{
	int i = 1, temp;
	boolean swapped = true;
	while(swapped)
	{
	swapped = false;
	for(int j=0; j < arr.length - i ; j++)
	{
	if(arr[j] > arr[j+1])
	{
	temp = arr[j];
	arr[j] = arr[j+1];
	arr[j+1] = temp;
	swapped = true;
	}
	}
	i++;
	}
	}
	public static void main(String []args)
	{
	int [] arr = { 12,34,32,5,6,2,3,4,23,34,233,64,64,3,634,43,322,3232,3};
	for (int i=0; i < arr.length; i++)
	System.out.print(" " +arr[i]);
	BBSort b = new BBSort();
	b.bubblesort(arr);
	System.out.println();
	for (int i=0; i < arr.length; i++)
	System.out.print(" " +arr[i]);
	}
	}

view raw BBSort.java hosted with ❤ by GitHub

Radix Sort in python

Here is the radix sort implementation in Python. The efficiency of the Radix Sort algorithm is based on the initial assumptions. According to the assumptions made it could be better or worse than other comparison based sorting algorithms. Mostly when the number of digits are constant it does better.

	# usr/bin/env python
	import math
	aList = [5,67,5,34,64,76,44,56,4,3,7,8,5]
	def radixsort( aList ):
	RADIX = 10
	maxLength = False
	tmp , placement = -1, 1
	while not maxLength:
	maxLength = True
	# declare and initialize buckets
	buckets = [list() for _ in range( RADIX )]
	# split aList between lists
	for i in aList:
	tmp = i / placement
	buckets[int(tmp % RADIX)].append( i )
	if maxLength and tmp > 0:
	maxLength = False
	# empty lists into aList array
	a = 0
	for b in range( RADIX ):
	buck = buckets[b]
	for i in buck:
	aList[a] = i
	a += 1
	# move to next digit
	placement *= RADIX
	print(aList)
	radixsort(aList)
	print(aList)

view raw RadixSort.py hosted with ❤ by GitHub