Merge-sort

Understand the efficiency and effectiveness of the merge-sort algorithm.

Merge-sort algorithm and its recursive structure

Merge-sort is one of the earliest algorithms designed for general-purpose stored-program computers. The algorithm was developed by John von Neumann in 1945 and described in detail in a publication with Herman Goldstine in 1947 as one of the first non-numerical programs for the EDVAC.

  1. Divide the input array into two subarrays of roughly equal size.
  2. Recursively merge-sort each of the subarrays.
  3. Merge the newly-sorted subarrays into a single sorted array.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy