Part I: Theoretical Part

$....$; Show different steps of merge$-$sort to sort the following array:

$10,3,15,43,8,94,23,45,53,8,14,22,9,37,77$

$q,$ ; Show different steps of the following union operations applied on a new disjoint set containing numbers $1,2,3,$dots,$9.$ Use union$-$by$-$size heuristic; i$.$e$.$ when merging two disjoint sets, the root of the one with more elements becomes the root of the merged set.

union $(1,3)$

union $(3,6)$

union $(2,5)$

union $(6,9)$

union $(1,2)$

union $(7,8)$

union $(4,8)$

union $(8,9)$

union $(9,5)$