Comparing Sorting Algorithms

This list is not already ordered. Because of this, Insertion Sort takes $O(n^2)$ time, Bubble Sort takes $O(n^2)$ time, and Mergesort takes $O(n \lg n)$ time.

Bubble Sort Pseudo Code do { swapped false ; for { int i = 1 to IndexofLastUnsortedElemtent -1 if LeftElement > RightElement swap(leftelement,rightelement) swappped true; } }while(swapped); Because the Sorting uses two loops to sort the input the BubbleSort Algorithm is equal to that of 2 loops which is N * N = N^2 . Insertion Sort Pseudo Code ( mark first elemtn as sorted ; 'extract' the element X; for j = lastSortedIndex down to 0 ; if current element j>x; move sorted element to the right by 1; break loop and insert the X right there . While Insertion Sort is quite better if it mostly sorted this array isn't so we take the worst possible case which is N^2;