previous | start | next

---

Merge Sort

• If the computer keeps dividing the vector into smaller and smaller subvectors, sorting each half and merging them back together.

  void merge_sort(vecotr<int>& a, int from, int to)
  {
     if (from == to) return;
     int mid = (from + to) / 2;
     /* sort the first and second half */
     merge_sort(a, from, mid);
     merge_sort(a, mid + 1, to);
     merge(a, from, mid, to);
  }
  

• The merge procedure discussed in the previous slide then merges the two sorted halves of the vector.

Merge Sort (mergsort.cpp)

---

previous | start | next