DataStructures

Data Structures and algorithms

Merge Sort

by

Merge Sort is a Divide and Conquer algorithm. How this works is, it first divides input array in two halves, calls itself for the two halves and then merges the two sorted halves.

The Idea is :

The mergeSort method should recursively sort the subarray array[l..r] i.e. after calling mergeSort(array,l,r) the elements from index l to index r of array should be sorted in ascending order.

Time complexity :

Time complexity of Merge Sort is O(nLogn) in all 3 cases (worst, average and best) as merge sort always divides the array into two halves and take linear time to merge two halves.

MergeSort Code :

class MergeSort {
	
	// Main method
	public static void main(String args[]) {
		int arr[] = { 11, 10, 12, 4, 6, 5 };

		System.out.println("Given Unsorted Array :");
		printArray(arr);

		MergeSort ob = new MergeSort();
		ob.mergeSort(arr, 0, arr.length - 1);

		System.out.println("\nSorted array :");
		printArray(arr);
	}

	// The method that sorts arr[l..r] using merge()
	void mergeSort(int arr[], int l, int r) {
		if (l < r) {
			// Find the middle point
			int m = (l + r) / 2;

			// Sort first and second halves
			mergeSort(arr, l, m);
			mergeSort(arr, m + 1, r);

			// Merge the sorted halves
			merge(arr, l, m, r);
		}
	}

	/*
	 * Merges two subarrays of arr[]. First subarray is arr[left..mid] Second
	 * subarray is arr[mid+1..right]
	 */
	void merge(int arr[], int l, int m, int r) {
		// Find sizes of two subarrays to be merged
		int size1 = m - l + 1;
		int size2 = r - m;

		/* Create temp arrays */
		int Left[] = new int[size1];
		int Right[] = new int[size2];

		/* Copy data to temp arrays */
		for (int i = 0; i < size1; ++i)
			Left[i] = arr[l + i];
		for (int j = 0; j < size2; ++j)
			Right[j] = arr[m + 1 + j];

		/* Merge the temp arrays */

		// Initial indexes of first and second subarrays
		int i = 0, j = 0;

		// Initial index of merged subarray array
		int k = l;

		while (i < size1 && j < size2) {
			if (Left[i] <= Right[j]) {
				arr[k] = Left[i];
				i++;
			} else {
				arr[k] = Right[j];
				j++;
			}
			k++;
		}

		/* Copy remaining elements of Left[] if any */
		while (i < size1) {
			arr[k] = Left[i];
			i++;
			k++;
		}

		/* Copy remaining elements of Right[] if any */
		while (j < size2) {
			arr[k] = Right[j];
			j++;
			k++;
		}
	}

	// method to print array of size n
	static void printArray(int arr[]) {
		for (int i = 0; i < arr.length; ++i)
			System.out.print(arr[i] + " ");
		System.out.println();
	}

}

OUTPUT

Given Unsorted Array :
11 10 12 4 6 5 

Sorted array :
4 5 6 10 11 12

Summary

In this tutorial, we saw the concept of merge sorting algorithm and we wrote a recursive merge sorting code in java. I suggest copy this code in your favorite IDE and test it.
I hope you liked it !

Bubble Sort

by

Bubble Sort is the simplest sorting algorithm that works by repeatedly checking and swapping the next adjacent elements if they are in wrong order.

Time complexity :

In Average/Worst Case : it usually takes n number of passes to sort an array and complexity becomes O(n^2)
In Best Case : it takes O(n) time complexity , and it happens only when the array is already sorted.

Bubble Sort Example :

// Java program to implement Bubble Sort 
class BubbleSortPT
{ 
  void bubbleSort(int arr[]) 
  { 
    int n = arr.length; 
    for (int i = 0; i < n-1; i++) 
    for (int j = 0; j < n-i-1; j++) 
    if (arr[j] > arr[j+1]) 
    { 
     // swap arr[j+1] and arr[i] 
     int temp = arr[j]; 
     arr[j] = arr[j+1]; 
     arr[j+1] = temp; 
    } 
  }

  /* Prints the array */
  void printArray(int arr[]) 
  { 
    int n = arr.length; 
    for (int i=0; i<n; ++i) 
    System.out.print(arr[i] + " "); 
    System.out.println(); 
  }

  // Main method to test the above code
  public static void main(String args[]) 
  { 
    BubbleSortPT ob = new BubbleSortPT(); 
    int arr[] = {64, 34, 25, 12, 22, 11, 90}; 

    ob.bubbleSort(arr); 
    System.out.println("Sorted array"); 
    ob.printArray(arr); 
  } 
}

OUTPUT

Sorted array
11 12 22 25 34 64 90

Summary

In this article we learnt about bubble sort and its time complexities.
Hope you liked it !