Tagged: time complexity

Merge Sort: Implementation and Analysis

Merge Sort Merge sort is a divide and conquer algorithm that sorts objects in O(n log n) time. Merge sort begins by dividing the input list into two sublists, and then continues to divide each subsequent sublist until we are left with a bunch of sublists that each contain one element. Each one element list is considered sorted. Next, Merge sort conquers each sorted sublist by repeatedly merging adjacent sorted...

Insertion Sort: Implementation and Analysis

Insertion Sort Overview Insertion sort is simple, but poorly performing sort algorithm that can sort a list in place. The Insertion sort algorithm works by splitting the input list into two partitions; a sorted part and an unsorted part. At the start of Insertion sort, the sorted part consists of 1 item; the first item in the input. Insertion sort then takes the first item of the unsorted part and...

Bubble Sort: Implementation and Analysis

Bubble Sort Overview Bubble Sort is a simple sort algorithm. When sorting a given list of items, in general, Bubble sort will make multiple passes over the list of items. During each pass, Bubble sort compares each adjacent pair of items. If the pair is in the correct order, Bubble sort does nothing and moves to the next adjacent pair. If the pair is out of order, Bubble sort swaps...