Untitled

#include <iostream>
using namespace std;

void printArray(int * arr, int n){
	
	for(int i=0; i <n; i++){
		cout << arr[i] << ", ";
	}
	cout << endl;
}

void bubbleSort(int * arr, int n){
	
	// n-1 iterations n = 5
	for(int itr =1; itr<=n-1; itr++){ // n-1 times
		
		// jth element with j+1th element
		for(int j=0; j < n - itr; j++){ // n-i times
			
			cout << "comparing " << arr[j] << " with " << arr[j+1] << endl;
			if(arr[j] > arr[j+1]){
				swap(arr[j], arr[j+1]);
			}
		}
	}
	
}

void optimisedBubbleSort(int * arr, int n){
	
	// n-1 iterations n = 5
	
	for(int itr =1; itr<=n-1; itr++){ // n-1 times
		
		bool isSwapped = false;
		
		// jth element with j+1th element
		for(int j=0; j < n - itr; j++){ // n-i times
			
			cout << "comparing " << arr[j] << " with " << arr[j+1] << endl;
			if(arr[j] > arr[j+1]){
				swap(arr[j], arr[j+1]);
				isSwapped = true;
			}
		}
		
		if(!isSwapped) {
			break;
		}
	}
	
}

int minIndexInArray(int * arr, int start, int end){
	
	int min = start;
	for(int i=start+1; i<end; i++){
		
		if(arr[i] < arr[min]){
			min = i;
		}
	}
	
	return min;
	
}

void selectionSort(int * arr, int n){
	
	for(int i = 0; i<n-1; i++){
		
		// find min element and swap
		int minIndex = minIndexInArray(arr, i, n);
		swap(arr[minIndex], arr[i]);
	}
}

void insertionSort(int * arr, int n){
	
	for(int i=1; i<n; i++){
		
		// int j = i-1;
		
		// while(j>=0 && arr[j] > arr[j+1]){
		// 	cout << "comparing " << arr[j] << " with " << arr[j+1] << endl; 
		// 	swap(arr[j], arr[j+1]);
		// 	j--;
		// }
		
		for(int j = i-1; j>=0; j--){
			if(arr[j] > arr[j+1]) {
				swap(arr[j], arr[j+1]);	
			}
		}
	}
	
}

int * mergeTwoSortedArrays(int * arr1, int n, int * arr2, int m){
	
	// create a new array
	int * newArray = new int[n+m];
	
	int i=0, j=0, k=0;
	while(i < n && j < m){
		
		if(arr1[i] > arr2[j]){
			newArray[k] = arr2[j];
			j++;
			
		} else {
			newArray[k] = arr1[i];
			i++; 
		}
		
		k++;
	}
	
	while(i < n){
		newArray[k] = arr1[i];
		i++; 
		k++;
	}
	
	while(j < m){
		newArray[k] = arr2[j];
		j++;
		k++;
	}
	
	return newArray;
}


int * mergeSort(int * arr, int start, int end){
	// base case
	if(start == end){
		int * newArray = new int[1];
		newArray[0] = arr[start];
		return newArray;
	}
	
	
	// divide and conquer
	int mid = (start + end)/2;
	int * lsh = mergeSort(arr, start, mid);
	int * rsh = mergeSort(arr, mid+1, end);
	
	int * finalArray = mergeTwoSortedArrays(lsh, mid-start+1, rsh, end - mid);
	return finalArray;
	
}


int main() {
	// your code goes here
	
	int n;
	cin >> n;
	
	int arr[n];
	for(int i=0; i<n; i++){
		cin >> arr[i];
	}
	
	printArray(arr, n);
	int * sortedArray = mergeSort(arr, 0, n-1);
	// bubbleSort(arr, n);
	// cout << "=======" << endl;
	// optimisedBubbleSort(arr, n);
	printArray(sortedArray, n);
	return 0;
}