COMP 250 Lecture Notes - Lecture 13: Linked List, Selection Sort, Dynamic Array
7 Dec 2017
School
Department
Course
Professor
Document Summary
In lecture 7, we saw three algorithms for sorting a list of n items. We saw that, in the worst case, all of these algorithm required o(n2) operations. Such algorithms will be unacceptably slow if n is large. To make this claim more concrete, consider that if n = 220 106 i. e one million, then n2 1012. Today we consider an alternative sorting algorithm that is much faster that these earlier o(n2) algorithms. If the list has just one number (n = 1), then do nothing. Otherwise, partition the list of n elements into two lists of size about n/2 elements each, sort the two individual lists (recursively, using mergesort), and then merge the two sorted lists. < 8, 10, 3, 11, 6, 1, 9, 7, 13, 2, 5, 4, 12 > . < 8, 10, 3, 11, 6, 1 > < 9, 7, 13, 2, 5, 4, 12 > . and sort these (by applying mergesort recursively):
