Sign InCoursewareNuggetsTutorials AboutClassesCodePad

Revisiting Sorting Algorithms

Remember selection sort and insersion sort? These simple sorting algorithms are convenient to use when sorting a small amount of data. However, their runtime complexity is O(n2), which makes them very slow when sorting a lot of data. Can we sort more efficiently? Take a look at the following list of n integers. Can you think of a way to sort them faster than O(n2)?

[45, 31, 5, 12, 8, 67, 9, 20, 22]

We have used the divide and conquer strategy to make searching faster.

  • Divide the problem into two or more smaller subproblems of the same or related type.
  • Conquer the subproblems by solving them recursively, until these become simple enough to be solved directly as base cases.
  • Combine the solutions to the subproblems into the solution for the original problem.

Can we use divide and conquer in sorting? Think of it for a moment before moving to the next page.

© CS Wonders·About·Classes·Cheatsheet