Merge Sort

[{"selector":"#anim-6f7a9503-0a56-4990-8a33-47a351482569","keyframes":{"transform":["translate3d(-115.07353%, 0px, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-2f076ed2-9648-44c0-9696-834581239af8","keyframes":[{"transform":"scale(1)","offset":0},{"transform":"scale(0.95)","offset":0.25},{"transform":"scale(1.05)","offset":0.75},{"transform":"scale(1)","offset":1}],"delay":0,"duration":600,"easing":"cubic-bezier(0.3, 0.0, 0.0, 1)","fill":"both","iterations":6}] [{"selector":"#anim-f3e0624f-7298-4594-acfb-c0ec05b9ad32","keyframes":{"transform":["translate3d(148.33334%, 0px, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-b9ecba8f-0412-4941-82e9-c5c13baa37c1 [data-leaf-element=\"true\"]","keyframes":{"transform":["translate3d(-7.89772701725232%, 0, 0)","translate3d(0%, 0, 0)"]},"delay":0,"duration":1000,"fill":"both"}] Algorithm Merge Sort All you need to know >> All you need to know >>

[{"selector":"#anim-7b021af5-ba1f-4acb-a068-fd500e80cf8b","keyframes":{"transform":["scale(3)","scale(1)"]},"delay":0,"duration":1000,"fill":"forwards"}] [{"selector":"#anim-c0da616e-3a07-40ed-92c6-d66739ca4853","keyframes":{"opacity":[0,1]},"delay":200,"duration":600,"easing":"cubic-bezier(0.4, 0.4, 0.0, 1)","fill":"both"}] [{"selector":"#anim-10242441-9c76-4c3e-a370-455c7a65055b [data-leaf-element=\"true\"]","keyframes":{"transform":["scale(4)","scale(1)"]},"delay":0,"duration":1000,"fill":"forwards"}] Merge sort is one of the most efficient sorting techniques and it’s based on the “divide and conquer” paradigm.

[{"selector":"#anim-ced6df1d-2653-4fd5-bdd8-e3f34aa64fa5","keyframes":{"transform":["translate3d(104.80000%, 0px, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.4, 0.4, 0.0, 1)","fill":"both"}] [{"selector":"#anim-0a0b931c-9c2a-492c-9ad5-bf611dd0d55c","keyframes":{"opacity":[0,1]},"delay":0,"duration":600,"easing":"cubic-bezier(0.4, 0.4, 0.0, 1)","fill":"both"}] [{"selector":"#anim-8082d34f-bfe4-426c-b4bf-7ef619940b3c","keyframes":{"transform":["scale(0.15)","scale(1)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.4, 0.4, 0.0, 1)","fill":"forwards"}] [{"selector":"#anim-2b7f4b7d-e4da-456e-b60b-643be5d36364","keyframes":{"transform":["translate3d(-112.42425%, 0px, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-e6c9843e-8bcd-4d95-8f0a-62d69d8f95d5 [data-leaf-element=\"true\"]","keyframes":{"transform":["translate3d(34.23295444978073%, 0, 0)","translate3d(0%, 0, 0)"]},"delay":0,"duration":1000,"fill":"both"}] [{"selector":"#anim-886305d8-63b3-4ab8-a61b-c61637aac90b","keyframes":[{"transform":"scale(1)","offset":0},{"transform":"scale(0.95)","offset":0.25},{"transform":"scale(1.05)","offset":0.75},{"transform":"scale(1)","offset":1}],"delay":0,"duration":600,"easing":"cubic-bezier(0.3, 0.0, 0.0, 1)","fill":"both","iterations":6}] In Mergesort, we take the mid index which is (beg index + end index)/2. Our array will always break into two subsequent arrays with approximately equal length. The Algorithm

[{"selector":"#anim-ddeb49d5-484c-4dff-af60-8d6fc3b70276","keyframes":{"transform":["translate3d(-112.72727%, 0px, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-3f0e0269-e2b1-4fe1-8a78-62eee154ad9f","keyframes":{"transform":["translate3d(108.85714%, 0px, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.4, 0.4, 0.0, 1)","fill":"both"}] [{"selector":"#anim-0cbdc0d4-5afd-4c7d-8281-a6b0fb9f5f6a","keyframes":{"opacity":[0,1]},"delay":0,"duration":600,"easing":"cubic-bezier(0.4, 0.4, 0.0, 1)","fill":"both"}] [{"selector":"#anim-1be54ea9-46c2-4d11-892a-b3bda7537fa4","keyframes":{"transform":["scale(0.15)","scale(1)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.4, 0.4, 0.0, 1)","fill":"forwards"}] [{"selector":"#anim-31a22fbb-4bd0-4c4b-9853-25d8e2108b99 [data-leaf-element=\"true\"]","keyframes":{"transform":["translate3d(9.687499755385314%, 0, 0)","translate3d(0%, 0, 0)"]},"delay":0,"duration":1000,"fill":"both"}] [{"selector":"#anim-eba191e2-a38a-45b4-a75e-1422dfdf3bf0","keyframes":[{"transform":"scale(1)","offset":0},{"transform":"scale(0.95)","offset":0.25},{"transform":"scale(1.05)","offset":0.75},{"transform":"scale(1)","offset":1}],"delay":0,"duration":600,"easing":"cubic-bezier(0.3, 0.0, 0.0, 1)","fill":"both","iterations":6}] Best Time Complexity: O(nlogn) Average Time Complexity: O(nlogn) Worst Time Complexity: O(nlogn) Time Complexity

[{"selector":"#anim-75a06f81-2ee3-40f4-8e12-657191ee9454","keyframes":{"transform":["translate3d(-112.42425%, 0px, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-fbfa66fd-b05b-4f86-b19c-a09865d30612","keyframes":{"transform":["translate3d(108.85714%, 0px, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-257dc43c-0a07-4d3a-bb4f-fcc19acc92c5 [data-leaf-element=\"true\"]","keyframes":{"transform":["scale(4)","scale(1)"]},"delay":0,"duration":1000,"fill":"forwards"}] [{"selector":"#anim-426a17e2-3ce8-42a4-93ce-2a51cde6ca44","keyframes":[{"transform":"scale(1)","offset":0},{"transform":"scale(0.95)","offset":0.25},{"transform":"scale(1.05)","offset":0.75},{"transform":"scale(1)","offset":1}],"delay":0,"duration":600,"easing":"cubic-bezier(0.3, 0.0, 0.0, 1)","fill":"both","iterations":6}] 'n' auxiliary space is required in Merge Sort implementation as all the elements are copied into an auxiliary array. Hence, Space Complexity is: O(n) Space Complexity

[{"selector":"#anim-90bee241-8551-41bc-b763-8ad153888898","keyframes":[{"transform":"scale(1)","offset":0},{"transform":"scale(0.95)","offset":0.25},{"transform":"scale(1.05)","offset":0.75},{"transform":"scale(1)","offset":1}],"delay":0,"duration":600,"easing":"cubic-bezier(0.3, 0.0, 0.0, 1)","fill":"both","iterations":6}] [{"selector":"#anim-30b3d2aa-ff8c-48cd-b36c-2194410d7aaa","keyframes":{"transform":["translate3d(104.80000%, 0px, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.4, 0.4, 0.0, 1)","fill":"both"}] [{"selector":"#anim-f24799e9-1004-406d-a4d9-555b7e6e24c0","keyframes":{"opacity":[0,1]},"delay":0,"duration":600,"easing":"cubic-bezier(0.4, 0.4, 0.0, 1)","fill":"both"}] [{"selector":"#anim-b5fab78c-15fd-4984-abd5-c0d1517562ba","keyframes":{"transform":["scale(0.15)","scale(1)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.4, 0.4, 0.0, 1)","fill":"forwards"}] [{"selector":"#anim-801ee91c-3c26-46c2-b902-96dfecef218c","keyframes":{"transform":["translate3d(-112.42425%, 0px, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] The Difference QuickSort Splitting of the array depends on the value of pivot and other array elements. It is non-stable. Merge Sort Splitting of array generally done on half It is stable.