Quicksort - O(nlgn)

@snehal do u mind writing code

public class QuickSort {
	
	public static void main(String[] args) {
		int[] a = new int[]{5,3,2,6,4,1,3,7};
		quicksort(a, 0, a.length-1);
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
	}
	
	public static void quicksort(int[] a, int left, int right){
		if(left < 0 || right >= a.length)
			return;
		
		if(right <= left)
			return;
		
		int endValue = a[right];//Choose the last element as the partition element
		
		int partitionIndex = partition(a, endValue, left, right-1);//Partition the array
		
		if(a[partitionIndex] < endValue){
			++partitionIndex;
		}
		
		swap(a, partitionIndex, right);
		
		quicksort(a, left, partitionIndex-1);
		quicksort(a, partitionIndex+1, right);
	}
	
	public static int partition(int a[], int endValue,int left,int right){
		while(left < right){
			if(a[left] < endValue){
				left++;
				continue;
			}
			if(a[right] >= endValue){
				right--;
				continue;
			}
			swap(a, left, right);
			++left;
			--right;
		}
		return left;
	}
	
	public static void swap(int[] a, int left, int right){
		int temp = a[left];
		a[left] = a[right];
		a[right] = temp;
	}
}

@clrs
How to find median in O(n)?

Another in place sorting method which takes O(nlogn) time is heapsort. It is slower than quicksort but it has the advantage that its worst case time is also O(nlogn)

if Shellsort is inplace then it takes only O(n^1.5)

Heap sort - it's inplace and O(nlog n)