Merge Sort: Small Sorted Parts Become One Sorted Array

Split the original eight values, merge them with two counters, and explain the work at each recursion level.

Step 1 of 7 · Follow the example

Start with two already sorted lists

Goal: Choose the next output from the two front values.

Take the small example [4,3,5,2]. After sorting each pair, we have [3,4] and [2,5]. Compare their first unused values:

Compare	Append	Values still unused
3 and 2	2	[3,4] and [5]
3 and 5	3	[4] and [5]
4 and 5	4	[] and [5]
Left list is empty	copy 5	[] and []

The result is [2,3,4,5]. There were 3 value comparisons during this merge, plus copying. Once a list is exhausted, copy the other list's remaining values; do not compare them with nonexistent elements.

Quick check · predict, then try

Choose the next merged value

The unused parts are [3,4] and [2,5]. Which value comes next?

Remember: Merging requires sorted inputs; it does not sort arbitrary halves by magic.

موضعك محفوظ تلقائيًا

العودة إلى الدراسة

المحاضرة 7 من 10

40 دقيقة تقريبًا

Merge Sort: Small Sorted Parts Become One Sorted Array

Split the original eight values, merge them with two counters, and explain the work at each recursion level.

تصفّح الدفتر

Step 1 of 7 · Follow the example

Start with two already sorted lists

Goal: Choose the next output from the two front values.

Take the small example [4,3,5,2]. After sorting each pair, we have [3,4] and [2,5]. Compare their first unused values:

Compare	Append	Values still unused
3 and 2	2	[3,4] and [5]
3 and 5	3	[4] and [5]
4 and 5	4	[] and [5]
Left list is empty	copy 5	[] and []

Quick check · predict, then try

Choose the next merged value

The unused parts are [3,4] and [2,5]. Which value comes next?

Remember: Merging requires sorted inputs; it does not sort arbitrary halves by magic.

موضعك محفوظ تلقائيًا

Start with two already sorted lists

Choose the next merged value

نفتح دفترك…

Start with two already sorted lists

Choose the next merged value