SORTING using MergeSore and QuickSort

A quick word about sorting using comparisons, each array with n items has n! permutations, if we look at the algorithm as a binary tree that each node to leaf is a premutation then the are n! node to leaf routes since each binary tree leaf routes is no more than 2^h where h is the height.

than 2^h > n! , and h > log n! , log n! is = n*logn.

MergeSort algorithm:

the algorithm takes nlogn since the recursive call to mergesort will be applied log n times since we can only divide the length of the array log n times. (log base 2).

in each call to mergeSort there will be a call to merge, merge is comparing the subArrays,

the longest comparison will take n/2 compares, since it will compare 2 sub-arrays of the original array, so total run time is n/2*logn which is nlogn.

QuickSort algorithm:

Hi i'm Maor