Sorting questions are among the most frequently asked topics in placement interviews. Many students prepare only Bubble Sort and Merge Sort, but companies often ask modified problems where sorting is only one part of the solution.
This article covers standard sorting questions, difficult interview problems, complete programs, and the mistakes students commonly make.
 

Table of Contents

---

Bubble Sort Implementation

Write a program to sort an array using Bubble Sort.
Answer:

// Java program to implement
// bubble sort
public class BubbleSortExample {
    public static void main(String args[]) 
    {
        int arr[] = {9,4,2,8,1};
        int n = arr.length;
        for(int i=0;in-1;i++) 
        {
            for(int j=0;jn-i-1;j++) 
            {
                if(arr[j]  arr[j+1]) 
                {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        System.out.println("Sorted Array:");
        for(int num:arr)
            System.out.print(num+" ");
    }
}

Output:

Sorted Array:
1 2 4 8 9 

Explanation:
Bubble sort compares adjacent elements and swaps them when required.

Input:
9 4 2 8 1
Output:
1 2 4 8 9

Time Complexity:

Best: O(n)
Average: O(n²)
Worst: O(n2)

Merge Sort Using Divide and Conquer

Sort an array using Merge Sort.
Answer:

// Java program to sort an array
// using merge sort
public class MergeSort {
    static void mergeSort(int arr[],int left,
                          int right) 
    {
        if(leftright) 
        {
            int mid=(left+right)/2;
            mergeSort(arr,left,mid);
            mergeSort(arr,mid+1,right);
            merge(arr,left,mid,right);
        }
    }
    static void merge(int arr[],int left,
                      int mid,int right) 
    {

        int n1=mid-left+1;
        int n2=right-mid;
        int L[]=new int[n1];
        int R[]=new int[n2];
        for(int i=0;in1;i++)
            L[i]=arr[left+i];
        for(int j=0;jn2;j++)
            R[j]=arr[mid+1+j];
        int i=0,j=0,k=left;
        while(in1 && jn2) 
        {
            if(L[i]=R[j])
                arr[k++]=L[i++];
            else
                arr[k++]=R[j++];
        }
        while(in1)
            arr[k++]=L[i++];
        while(jn2)
            arr[k++]=R[j++];
    }
    public static void main(String args[]) 
    {
        int arr[]={7,3,9,1,5};
        mergeSort(arr,0,arr.length-1);
        for(int x:arr)
            System.out.print(x+" ");
    }
}

Output:

1 3 5 7 9 

Explanation:
Merge Sort divides the array into smaller pieces and then merges them after sorting.
Time Complexity:

O(n log n)

Sort Array Containing Only 0, 1, and 2

This looks easy, but interviewers expect an optimized solution.

Input:
2 0 1 2 1 0
Output:
0 0 1 1 2 2

Answer:

// Java program to sort array containing
// only 0,1, and 2
public class Sort012 {
    public static void main(String args[]) 
    {
        int arr[]={2,0,1,2,1,0};
        int low=0;
        int mid=0;
        int high=arr.length-1;
        while(mid=high) 
        {
            if(arr[mid]==0) 
            {
                int temp=arr[mid];
                arr[mid]=arr[low];
                arr[low]=temp;
                low++;
                mid++;
            }
            else if(arr[mid]==1)
                mid++;
            else 
            {
                int temp=arr[mid];
                arr[mid]=arr[high];
                arr[high]=temp;
                high--;
            }
        }
        for(int x:arr)
            System.out.print(x+" ");
    }
}

Output:

0 0 1 1 2 2 

Why Companies Ask This?
Many students use normal sorting methods with:
O(n log n)
Expected solution:
O(n)

Minimum Swaps Required to Sort Array

Find the minimum number of swaps needed.

Input:
7 1 3 2 4 5 6
Output:
5

Answer:

// Java program to find the minimum
// swaps required to sort an array
import java.util.*;
public class MinimumSwaps {
    static class Pair 
    {
        int value;
        int index;
        Pair(int value,int index) 
        {
            this.value=value;
            this.index=index;
        }
    }
    public static void main(String args[]) 
    {
        int arr[]={7,1,3,2,4,5,6};
        Pair pairs[]=new Pair[arr.length];
        for(int i=0;iarr.length;i++)
            pairs[i]=new Pair(arr[i],i);
        Arrays.sort(pairs,
                   (a,b)-a.value-b.value);
        boolean visited[]=new boolean[arr.length];
        int swaps=0;
        for(int i=0;iarr.length;i++) 
        {
            if(visited[i] || pairs[i].index==i)
                continue;
            int cycle=0;
            int j=i;
            while(!visited[j]) 
            {
                visited[j]=true;
                j=pairs[j].index;
                cycle++;
            }
            swaps += cycle-1;
        }
        System.out.println(swaps);
    }
}

Output:

5

Explanation:
This is not just a sorting question.
Interviewers use it to check:

1. Index mapping
2. Cycle detection
3. Optimization logic

Count Inversions in Array

Find all pairs where arr[i] arr[j] and i j.

Input:
5 3 2 4 1
Output:
8

Answer:

// Java program to count inversions 
// in an array
public class CountInversions {
    static int merge(int arr[],int temp[],
                     int left,int mid,int right) 
    {
        int i=left;
        int j=mid;
        int k=left;
        int inv=0;
        while(i=mid-1 && j=right) 
        {
            if(arr[i]=arr[j])
                temp[k++]=arr[i++];
            else 
            {
                temp[k++]=arr[j++];
                inv += mid-i;
            }
        }
        while(i=mid-1)
            temp[k++]=arr[i++];
        while(j=right)
            temp[k++]=arr[j++];
        for(i=left;i=right;i++)
            arr[i]=temp[i];
        return inv;
    }
    static int mergeSort(int arr[],int temp[],
                         int left,int right) 
    {
        int inv=0;
        if(rightleft) 
        {
            int mid=(left+right)/2;
            inv += mergeSort(arr,temp,left,mid);
            inv += mergeSort(arr,temp,mid+1,right);
            inv += merge(arr,temp,left,mid+1,right);
        }
        return inv;
    }
    public static void main(String args[]) 
    {
        int arr[]={5,3,2,4,1};
        int temp[]=new int[arr.length];
        System.out.println(mergeSort(arr,temp,
                                     0,arr.length-1));
    }
}

Output:

8

This problem combines:

1. Merge sort
2. Counting logic
3. Optimization

Common Mistakes Students Make in Sorting Questions

1. Using Bubble Sort for Every Problem
Many students remember Bubble Sort first and apply it everywhere.
Example:

Finding minimum swaps using:

O(n²)

Expected solution:

O(n log n)

Interviewers usually look for optimized approaches.

2. Ignoring Time Complexity
Students write working code but cannot explain complexity.
Example:

Bubble Sort:
O(n²)
Merge Sort:
O(n log n)
Quick Sort average:
O(n log n)

Always mention complexity after writing code.

3. Forgetting Edge Cases
Many programs work only for normal input.
Always test:

• Empty array
• Single element
• Duplicate values
• Already sorted array
• Reverse sorted array

Placement platforms often include these cases.

4. Confusing Stable and Unstable Sorting
Stable sorting keeps the order of equal elements.
Stable:

1. Bubble Sort
2. Merge Sort

Unstable:

1. Quick Sort
2. Selection Sort

Interviewers sometimes ask this after coding.

5. Solving Modified Problems Like Normal Sorting
Students see the word “sort” and immediately start writing sorting algorithms.
Questions such as:

• Minimum swaps
• Count inversions
• Top K frequent elements
• Frequency sorting
• Merge K arrays

need extra logic beyond sorting.

Conclusion

Students usually spend too much time memorizing Bubble Sort, Selection Sort, and Merge Sort. Real placement questions are often modified versions where sorting becomes only one step.
Spend extra practice time on:

• Inversion counting
• Minimum swaps
• Frequency based sorting
• K sorted arrays
• Top K problems
• Stream based sorting questions

These questions appear much more often in coding rounds and online assessments.