Merge sort
class MergeSort
// Merge two subarrays
void merge(int arr[], int p, int q, int r)
int n1 = q - p + 1;
int n2 = r - q;
int Left[] = new int[n1];
int Right[] = new int[n2];
for (int i = 0; i < n1; i++)
Left[i] = arr[p + i];
for (int j = 0; j < n2; j++)
Right[j] = arr[q + 1 + j];
// Maintain current index of sub-arrays
int i, j, k;
i = 0;
j = 0;
k = p;
while (i < n1 && j < n2)
if (Left[i] <= Right[j])
arr[k] = Left[i];
i++;
else
arr[k] = Right[j];
j++;
k++;
while (i < n1)
arr[k] = Left[i];
i++;
k++;
}
while (j < n2) {
arr[k] = Right[j];
j++;
k++;
// Divide the array into two subarrays, sort them and merge them
void mergeSort(int arr[], int left, int right)
if (left < right)
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge the sorted subarrays
merge(arr, left, mid, right);
}
void printArray(int arr[])
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
class MergeSortApp
public static void main(String args[])
int arr[] = { 66,33,11,44,00,88,22,99,55,77};
System.out.println("Given array:");
for(int i=0;i<arr.length;i++)
System.out.print(“ “ +arr[i]);
MergeSort obj = new MergeSort();
obj.mergeSort(arr, 0, arr.length - 1);
System.out.println("Sorted array:");
printArray(arr);
}
Quick Sort
import java.util.Arrays;
class Quicksort
static int partition(int array[], int low, int high)
int pivot = array[high];
int i = (low - 1);
for (int j = low; j < high; j++)
if (array[j] <= pivot)
i++;
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
int temp = array[i + 1];
array[i + 1] = array[high];
array[high] = temp;
return (i + 1);
static void quickSort(int array[], int low, int high)
if (low < high)
int pi = partition(array, low, high);
quickSort(array, low, pi - 1);
quickSort(array, pi + 1, high);
class QuickSortApp
public static void main(String args[])
int data[] = { 66,33,11,55,22,77,00,99,44,88};
System.out.println("Given Unsorted Array");
System.out.println(Arrays.toString(data));
int size = data.length;
quickSort(data, 0, size - 1);
System.out.println(" Sorted Array : ");
System.out.println(Arrays.toString(data));
