Heap Sort(max heap)

 public class HeapSortNew {

    public static void main(String[] args) {

        int[] arr = {4,1,7,2,3,8,10};

        int n= arr.length;

        for(int i=n/2-1;i>=0;i--){

            heapify(arr,n,i);

        }

        System.out.println(Arrays.toString(arr));

        for(int i=n-1;i>=0;i--){

            swap(arr,i,0);

            heapify(arr,i,0);

        }

        System.out.println(Arrays.toString(arr));

    }

    static void heapify(int[] arr, int n, int i){

        int l = 2*i+1;

        int r = 2*i+2;

        int largest = i;

        if(l<n){

            if(arr[l]>arr[largest]){

                largest = l;

            }

        }

        if(r<n){

            if(arr[r]>arr[largest]){

                largest = r;

            }

        }

        //if value get updated

        if(largest!=i){

            swap(arr,i,largest);

            heapify(arr,n,largest);

        }

    }

    static void swap(int[] arr, int i, int j){

        int temp = arr[i];

        arr[i]  =arr[j];

        arr[j]=temp;

    }

}

output:

[10, 3, 8, 2, 1, 4, 7]

[1, 2, 3, 4, 7, 8, 10]he

MergeSort Program

Merge Sort:

public class MergeSort2 {

    public static void main(String args[]) {
        int[] arr = {1,12,3,8,2,1,7,9};
        mergeSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
   
    public static void mergeSort(int[] arr, int start, int end) {
        if(start<end) {                               //check start < mid then find mid and divide arr in parts 
            int mid = (start + end)/2 ;
            mergeSort(arr, start, mid);
            mergeSort(arr, mid+1, end);
            merge(arr, start, mid, end); //merge
        }
    }
   
    public static void merge(int[] arr, int start, int mid, int end) {
        int p = start ;
        int q = mid+1;
       
        int[] localArr = new int[end-start+1];
        int k = 0;
        for(int i=start;i<=end;i++) {
            if(p>mid) {
                localArr[k] = arr[q];
                k++;
                q++;
            }else if(q>end) {
                localArr[k] = arr[p];
                k++;
                p++;
            }else if(arr[p]<arr[q]) {
                localArr[k] = arr[p];
                p++;
                k++;
            }else {
                localArr[k]  =arr[q];
                q++;
                k++;
            }
        }
       
        for(int i=0;i<localArr.length;i++) {
            arr[start]  = localArr[i];
            start++;
        }
       
       
    }
   
}

How merge method work:
take an example below
[1,12 ,3,8 ||||||| ,2,1,7,9] start = 0,mid = 1,end = 3
we want to merge 0 to 3

p = 0
q=  mid+1 = 2;
take localarr of size end-start+1 = 4
k=0
loop---> start to < = end
if p reaches to mid then only right part need to insert localarr
if(p>mid) {
                localArr[k] = arr[q];
                k++;
                q++;
            }
if q reaches to end then only left part need to insert into localarr
else if(q>end) {
                localArr[k] = arr[p];
                k++;
                p++;
            }

if arr[p] <arr[q] it means need to insert p position element to localarr and increemt p

else if(arr[p]<arr[q]) {
                localArr[k] = arr[p];
                p++;
                k++;
            }

if arr[p]>arr[q] it means need to insert q position element to localarr and increment q
 else {
                localArr[k]  =arr[q];
                q++;
                k++;
            }

loop exit

now need to insert localarr to original array
  for(int i=0;i<localArr.length;i++) {
            arr[start]  = localArr[i];
            start++;
        }

QuickSort Program

QuickSort:

[5,9,3,15,13,7,1,8,18,14,4]

Steps:

we will choose first element as pivot
move all less than pivot on one side and other on one side

so we need to find the pivot element position
then partition in 2 parts first is before pivot and other is after pivot

public class QuickSort {
   
    public static void main(String args[]) {
        int arr[] = {10,3,16,8,9,1,15,6,18};
        quick_sort(arr,0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
   
    static void quick_sort ( int A[ ] ,int start , int end ) {
           if( start < end ) {
                //stores the position of pivot element
                 int piv_pos = partition (A,start , end ) ;    
                 quick_sort (A,start , piv_pos -1);    //sorts the left side of pivot.
                 quick_sort ( A,piv_pos +1 , end) ; //sorts the right side of pivot.
           }
        }
   
    static int partition ( int A[],int start ,int end) {
        int i = start + 1;
        int piv = A[start] ;            //make the first element as pivot element.
        for(int j =start + 1; j <= end ; j++ )  {
        /*rearrange the array by putting elements which are less than pivot
           on one side and which are greater that on other. */

              if ( A[ j ] < piv) {
                     swap (A ,i , j );
                i += 1;
            }
       }
       swap ( A,start ,i-1  ) ;  //put the pivot element in its proper place.
       return i-1;                      //return the position of the pivot
    }
   
    public static void swap(int[] A,int first, int second) {
        int temp = A[first];
        A[first] = A[second];
        A[second] = temp;
    }
   
}


How partition work in above:
start = 0 , end = 10
[5,9,3,15,13,7,1,8,18,14,4]
piv = A[start] = 5
i = start+1 = 1;
loop--> j=start+1 to <=end and j++

first round of loop:  a[j]>piv so nothing change
                                  i= 1, j=2
second round of loop: a[j]<piv so swap i with j and increase i by1
  [5,3,9,15,13,7,1,8,18,14,4]
       i = 2, j=3
third round of loop:  a[j]>piv so nothing change
i=2,j=4 
fourth round of loop:  a[j]>piv so nothing change
i=2,j=5
fifth round of loop:  a[j]>piv so nothing change
i=2,j=6
seventh round of loop: a[j]<piv so swap i with j and increase i by1
  [5,3,1,15,13,7,9,8,18,14,4]
       i = 3, j=7
next few round no change till i=3, j=9
in last round i=3,j=10
a[j]<piv so swap i with j and increase i by1
  [5,3,1,4,13,7,9,8,18,14,15]
       i = 4


now loop break move pivot element to actual position
swap i-1 with start(pivot)

now pivot moved to actual postion

then we will sort the leftside of pivot and right side