Implement sqrt and parity-based array rearrangement

You are given two independent coding tasks.

Task 1: Implement Square Root Without Math Library

Implement a function that computes the square root of a non-negative number without using any built-in square root or exponentiation functions from math libraries.

• Input: A non-negative real number x .
• Output: A real number y such that y * y approximates x within a specified error bound (for example, absolute error < 1e-6 ).
• Constraints:
  • You may use basic arithmetic operations ( + , - , * , / ) and control flow.
  • You may not call built-in functions like sqrt , pow , etc.
• Clarifications to handle in code:
  • What should the function return when x = 0 ?
  • How do you handle very large or very small positive values of x ?

Define the function signature in a language of your choice, document the precision assumption you make (e.g., 1e-6), and implement the algorithm.

Task 2: Rearrange Array by Index Parity

You are given an array of integers. You must rearrange its elements in-place (i.e., using O(1) extra space) so that all numbers at even positions (using 1-based indexing) are strictly smaller than all numbers at odd positions.

• Input: An integer array arr of length n .
• Output: The same array, modified in place, such that:
  • If we number positions starting from 1, then every element at an even position (indices 2, 4, 6, ... ) is strictly less than every element at an odd position (indices 1, 3, 5, ... ).
  • Any arrangement that satisfies this property is acceptable.
• Example:
  • Input: [1, 2, 3, 4, 5]
  • One valid output: [5, 1, 4, 2, 3]
    • Odd positions (1, 3, 5) → values [5, 4, 3]
    • Even positions (2, 4) → values [1, 2]
    • Every even-position value ( 1, 2 ) is less than every odd-position value ( 3, 4, 5 ).
• Constraints/requirements:
  • The rearrangement must be done in-place (only O(1) extra storage).
  • Aim for an efficient algorithm (e.g., O(n log n) or better time complexity).

Describe your algorithm, its time and space complexity, then implement it.